区间DP
f[l][r][0/1]表示生成目标序列中的区间[l,r]，最后一个数是a[l]/a[r] 的方案数
边界：
f[i][i][0]=1
转移：
f[l][r][0]=(a[l]<a[l+1]?f[l+1][r][0]:0)+(a[l]<a[r]?f[l+1][r][1]:0);
f[l][r][1]=(a[r]>a[l]?f[l][r-1][0]:0)+(a[r]>a[r-1]?f[l][r-1][1]:0);
#include<iostream> #include<cstdio> using namespace std; #define MAXN 1010 #define MOD 19650827 int n,a[MAXN],f[MAXN][MAXN][2]; int main(){ scanf("%d",&n); for(int i=1;i<=n;i++) scanf("%d",&a[i]); for(int i=1;i<=n;i++) f[i][i][0]=1; for(int len=2;len<=n;len++) for(int l=1;l+len-1<=n;l++){ int r=l+len-1; f[l][r][0]=((a[l]<a[l+1]?f[l+1][r][0]:0)+(a[l]<a[r]?f[l+1][r][1]:0))%MOD; f[l][r][1]=((a[r]>a[l]?f[l][r-1][0]:0)+(a[r]>a[r-1]?f[l][r-1][1]:0))%MOD; } printf("%d\n",(f[1][n][0]+f[1][n][1])%MOD); return 0; }
[HNOI2010]CHORUS 合唱队 （洛谷P3205）
原文：https://www.cnblogs.com/yjkhhh/p/9206272.html