题意: 合唱队一共N个人，第i个人的身高为Hi米(1000<=Hi<=2000),并已知任何两个人的身高都不同。假定最终排出的队形是A 个人站成一排，为了简化问题，小A想出了如下排队的方式：他让所有的人先按任意顺序站成一个初始队形，然后从左到右按以下原则依次将每个人插入最终棑排出的队形中：

• 第一个人直接插入空的当前队形中。

  
  讯享网

• 对从第二个人开始的每个人，如果他比前面那个人高(H较大)，那么将他插入当前队形的最右边。如果他比前面那个人矮(H较小)，那么将他插入当前队形的最左边。

当N个人全部插入当前队形后便获得最终排出的队形。

>> face <<

Strategy: 区间dp or 记忆化搜索

状态: $\{\begin{array}{l}dp[l][r][0]\to 可得到理想区间[l,r],并且l后入的方案数\\ dp[l][r][1]\to 可得到理想区间[l,r]并且r后入的方案数\end{array}$

目标: $(dp[1][n][0]+dp[1][n][1])\%mod$

边界: $dp[i][i][1]=1;$

合法判断: 后插的数与之前的数满足一定的大小关系才能进行转移

转移方程: 区间dp, 枚举未知, 让所有能转移到该未知的状态来转移, 方程见上

attention:

• 状态的设计
• 边界初始化
• 为啥dp[i][i][1]不能等于1 ? hack: 1 1会输出2

双倍经验:

@author: jasonleft 区间dp #include <bits/stdc++.h> #include <bits/extc++.h> #define _rep(i, a, b) for (int i = (a); i <= (b); ++i) #define _rev(i, a, b) for (int i = (a); i >= (b); --i) #define _for(i, a, b) for (int i = (a); i < (b); ++i) #define _rof(i, a, b) for (int i = (a); i > (b); --i) #define ll long long #define db double #define oo 0x3f3f3f3f #define eps 0.00001 #define all(x) x.begin(), x.end() #define met(a, b) memset(a, b, sizeof(a)) #define what_is(x) cerr << #x << " is " << x << endl #define lowbit(x) x &(-x) using namespace std; const int maxn = 1e3 + 9; const int mod = ; int dp[maxn][maxn][2], n, a[maxn]; int main() { 
    ios::sync_with_stdio(0); cin >> n; _rep(i, 1, n) { 
    cin >> a[i]; dp[i][i][0] = 1; } _rep(len, 2, n) { 
    _rep(l, 1, n - len + 1) { 
    int r = l + len - 1; dp[l][r][0] = (dp[l + 1][r][0] * (a[l] < a[l + 1]) + dp[l + 1][r][1] * (a[l] < a[r])) % mod; dp[l][r][1] = (dp[l][r - 1][0] * (a[r] > a[l]) + dp[l][r - 1][1] * (a[r] > a[r - 1])) % mod; } } cout << (dp[1][n][0] + dp[1][n][1]) % mod << endl; } 

第一次回顾

• 状态很难想 可以从这里开始, 每个区间[l,r]都由两种方式转移过来, 一种是最后一个转移过来的是l, 另一种是最后一个转移过来的是r, 假设最后一个转移过来的是r, 那么转移之前的区间是[l,r-1], 这时我们就要讨论这个区间的最后一个转移过来的是谁了, 如果是l, 那么我们要满足新数大于a[l], 否则不能放右边, 如果是r-1,那么依旧要满足新数大于a[r-1], 这才能贡献到转移区间[l,r]最后一个是r的情况, 同理最后一个是l的情况也类似.
• 转移很简单

讯享网/* * I Love Coding! * * .::::. * .::::::::. * ::::::::::: * ..:::::::::::' * '::::::::::::' * .:::::::::: * '::::::::::::::.. * ..::::::::::::. * ``:::::::::::::::: * ::::``:::::::::' .:::. * ::::' ':::::' .::::::::. * .::::' :::: .:::::::'::::. * .:::' ::::: .:::::::::' ':::::. * .::' :::::.:::::::::' ':::::. * .::' ::::::::::::::' ``::::. * ...::: ::::::::::::' ``::. * ````':. ':::::::::' ::::.. * '.:::::' ':'````.. */ #include <bits/stdc++.h> #include <bits/extc++.h> #define _rep(i, a, b) for (int i = (a); i <= (b); ++i) #define _rev(i, a, b) for (int i = (a); i >= (b); --i) #define _for(i, a, b) for (int i = (a); i < (b); ++i) #define _rof(i, a, b) for (int i = (a); i > (b); --i) #define ll long long #define db double #define oo 0x3f3f3f3f #define eps 0.00001 #define all(x) x.begin(), x.end() #define met(a, b) memset(a, b, sizeof(a)) #define id(x) ((x + 8)) #define what_is(x) cerr << #x << " is " << x << endl #define lowbit(x) x &(-x) const int maxn = 1e3 + 9; const int mod = ; using namespace std; ll a[maxn], n, dp[maxn][maxn][2]; //dp[l][r][0] : r最后入lr区间 int main() { 
    ios::sync_with_stdio(0); int n; cin >> n; _rep(i, 1, n) { 
    cin >> a[i]; dp[i][i][1] = 1; } _rep(len, 2, n) { 
    _rep(l, 1, n - len + 1) { 
    int r = l + len - 1; dp[l][r][0] = (dp[l][r - 1][0] * (a[r] > a[r - 1]) + dp[l][r - 1][1] * (a[r] > a[l])) % mod; dp[l][r][1] = (dp[l + 1][r][0] * (a[l] < a[r]) + dp[l + 1][r][1] * (a[l + 1] > a[l])) % mod; } } cout << (dp[1][n][0] + dp[1][n][1]) % mod << endl; }