BZOJ 1996: [Hnoi2010]chorus 合唱队(dp)

时间:2022-07-01 19:17:48

BZOJ 1996: [Hnoi2010]chorus 合唱队(dp)

简单的dp题..不能更水了..

---------------------------------------------------------------

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#define rep(i,n) for(int i=0;i<n;++i)
#define clr(x,c) memset(x,c,sizeof(x))
using namespace std;
const int maxn=1000+5;
const int mod=19650827;
int n;
int goal[maxn];
int d[maxn][maxn][2];//0放入左,1放入右
int dp(int l,int r,int op) {
int &ans=d[l][r][op];
if(ans>=0) return ans;
ans=0;
if(op) {
if(goal[l]<goal[r]) ans=dp(l,r-1,0);
if(l!=r-1 && goal[r-1]<goal[r]) (ans+=dp(l,r-1,1))%=mod;
} else {
if(goal[l+1]>goal[l]) ans=dp(l+1,r,0);
if(l+1!=r && goal[r]>goal[l]) (ans+=dp(l+1,r,1))%=mod;
}
return ans%=mod;
}
int main()
{
// freopen("test.in","r",stdin);
// freopen("test.out","w",stdout);
clr(d,-1);
scanf("%d",&n);
rep(i,n) d[i][i][0]=d[i][i][1]=1;
rep(i,n) scanf("%d",&goal[i]);
printf("%d\n",(dp(0,n-1,0)+dp(0,n-1,1))%mod);
return 0;
}

---------------------------------------------------------------

1996: [Hnoi2010]chorus 合唱队

Time Limit: 4 Sec  Memory Limit: 64 MB
Submit: 1045  Solved: 672
[Submit][Status][Discuss]

Description

BZOJ 1996: [Hnoi2010]chorus 合唱队(dp)

Input

BZOJ 1996: [Hnoi2010]chorus 合唱队(dp)

Output

BZOJ 1996: [Hnoi2010]chorus 合唱队(dp)

Sample Input

4
1701 1702 1703 1704

Sample Output

8

HINT

BZOJ 1996: [Hnoi2010]chorus 合唱队(dp)