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

Description

Input

Output

Sample Input

4
1701 1702 1703 1704

Sample Output

8

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

 #include<iostream>

 #include<cstring>

 #include<cstdio>

 #define N (1000+10)

 using namespace std;

 int n,a[N],f[N][N][];

 int main()

 {

     scanf("%d",&n);

     for (int i=; i<=n; ++i)

         scanf("%d",&a[i]);

     for (int i=; i<=n; ++i)

         f[i][i][]=;

     for (int i=; i<=n; ++i)

         for (int j=; j<=n; ++j)

         {

             int x=j,y=x+i-;

             f[x][y][]+=f[x+][y][]*(a[x]<a[x+]);

             f[x][y][]+=f[x+][y][]*(a[x]<a[y]);

             f[x][y][]+=f[x][y-][]*(a[y]>a[x]);

             f[x][y][]+=f[x][y-][]*(a[y]>a[y-]);

             f[x][y][]%=;

             f[x][y][]%=;

         }

     printf("%d",(f[][n][]+f[][n][])%);

 }