BZOJ1996:[HNOI2010]CHORUS 合唱队(区间DP)

Description

Input

Output

Sample Input

4
1701 1702 1703 1704

Sample Output

HINT

Solution

辣鸡guide真难用
Dev赛高！
一道蛮水的区间DP
很容易发现，当前要放进来的人只和已经排出的队伍的两端的大小关系有关
就很容易设计状态表示f[x][y][0/1]表示当前已经排好[x,y]，且这次放的人在最左/最右边
答案即为f[1][n][0]+f[1][n][1]
初始化状态要设f[i][i][0]=1
答案记得取模

Code

 1 #include<iostream>
 2 #include<cstring>
 3 #include<cstdio>
 4 #define N (1000+10)
 5 using namespace std;
 6 int n,a[N],f[N][N][2];
 7 int main()
 8 {
 9     scanf("%d",&n);
10     for (int i=1; i<=n; ++i)
11         scanf("%d",&a[i]);
12     for (int i=1; i<=n; ++i)
13         f[i][i][0]=1;
14     for (int i=2; i<=n; ++i)
15         for (int j=1; j<=n; ++j)
16         {
17             int x=j,y=x+i-1;
18             f[x][y][0]+=f[x+1][y][0]*(a[x]<a[x+1]);
19             f[x][y][0]+=f[x+1][y][1]*(a[x]<a[y]);
20             f[x][y][1]+=f[x][y-1][0]*(a[y]>a[x]);
21             f[x][y][1]+=f[x][y-1][1]*(a[y]>a[y-1]);
22             f[x][y][0]%=19650827;
23             f[x][y][1]%=19650827;
24         }
25     printf("%d",(f[1][n][0]+f[1][n][1])%19650827);
26 }