题目链接：https://www.lydsy.com/JudgeOnline/problem.php?id=1996
要想到是区间DP。。。
如果单纯设dp[l][r]表示摆放区间[l,r]的方案数，发现无法转移，所以可以增加一维用于记录最后一个元素是加到左边还是右边。
然后分类讨论即可，对于dp[l][r][0]，讨论第i个是从dp[l+1][r][0](a[l]<a[l+1])还是dp[l+1][r][1](a[l]<a[r])转移来的，dp[l][r][1]同理。
边界的处理也需要注意，一开始写的是dp[i][i][0]=dp[i][i][1]=1，但输入样例发现输出是样例的两倍，然后把这里改成dp[i][i][0]=1就对了，应该是因为之前那样会将单个元素的方案数统计两遍。
1 #include <cstdio> 2 3 const int maxn = 1005, mod = 19650827; 4 5 int a[maxn], dp[maxn][maxn][2]; 6 //dp[l][r][0]表示摆放区间[l,r]最后一个是插到左边的方案数 7 8 int main() { 9 int n; 10 scanf("%d", &n); 11 for (int i = 1; i <= n; ++i) { 12 scanf("%d", &a[i]); 13 dp[i][i][0] = 1; //防止单个元素时统计两遍 14 } 15 for (int l = n - 1; l >= 1; --l) 16 for (int r = l + 1; r <= n; ++r) { 17 dp[l][r][0] = ((a[l] < a[l + 1]) * dp[l + 1][r][0] + (a[l] < a[r]) * dp[l + 1][r][1]) % mod; 18 dp[l][r][1] = ((a[r] > a[l]) * dp[l][r - 1][0] + (a[r] > a[r - 1]) * dp[l][r - 1][1]) % mod; 19 } 20 printf("%d", (dp[1][n][0] + dp[1][n][1]) % mod); 21 return 0; 22 }
原文：https://www.cnblogs.com/Mr94Kevin/p/9894835.html
