题解 P3205 【[HNOI2010]CHORUS 合唱队】
区间DP，用记忆化搜索实现
没有卡常，10分钟做出来，还跑最快代码最短，写个题解留念下
dp[i][j]表示现在还剩[i,j]这一段没有处理，op=0表示上一次删掉的是左边的，op=1表示上次删的右边的，方案数
转移的话条件就是从左边转移那么这次丢掉的要比上一次大，从右边则反
临界条件就是l==r
#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;
}