题解 P3205 【[HNOI2010]CHORUS 合唱队】

# 区间DP，用记忆化搜索实现 ~~没有卡常，10分钟做出来，还跑最快代码最短，写个题解留念下~~ dp[i][j]表示现在还剩[i,j]这一段没有处理，op=0表示上一次删掉的是左边的，op=1表示上次删的右边的，方案数 转移的话条件就是从左边转移那么这次丢掉的要比上一次大，从右边则反 临界条件就是l==r ```cpp #include<cstdio> #include<cstdlib> #include<cstring> using namespace std; const int MAXN=1010; const int mod=19650827; int N,A[MAXN],dp[MAXN][MAXN][2]; int DFS(int l,int r,int op) { if(l==r) dp[l][r][op]=((A[l]<A[l+1]&&op)|(A[l]>A[l-1]&&!op))?1:0; if(dp[l][r][op]!=-1) return dp[l][r][op]; int ans=0; if(op==1) { if(A[l]<A[r+1]) ans+=DFS(l+1,r,0); if(A[r]<A[r+1]) ans+=DFS(l,r-1,1); } else { if(A[l]>A[l-1]) ans+=DFS(l+1,r,0); if(A[r]>A[l-1]) ans+=DFS(l,r-1,1); } return dp[l][r][op]=ans%mod; } int main() { scanf("%d",&N);memset(dp,-1,sizeof(dp)); for(int i=1;i<=N;i++) scanf("%d",&A[i]); printf("%d\n",DFS(1,N,0)); return 0; } ``` ### 顺便安利一波[我的博客](https://www.cnblogs.com/xzyxzy/)