1996: [Hnoi2010]chorus 合唱队

Description

Input

Output

Sample Input

4

1701 1702 1703 1704

Sample Output

8

HINT

 

Source

题解：

讲得详细一点好了。。

对于某个序列，我们没加入一个数，要么放到最前面，要么放到最后面。

对于每一个区间也是一样，a[i...j]，最后放进来的不是a[i]就是a[j]。。。

我们定义一个数组f[i][j][k]

k=0表示在区间[i,j] ，最后添进来的数是a[i]的方案种数

k=1则最后添进a[j]

转移我想也是很好写的，最后在看看题目吧，可能题目意思理解有误（每放入一个是于上次放入的比较）。。

#include
     
      #include
      
       using namespace std;const int M=19650827;const int N=1005;int n,i,j,a[N],f[N][N][2];int main(){    scanf("%d",&n);    for(i=1;i<=n;i++)        scanf("%d",&a[i]);    for(i=1;i<=n;i++)        f[i][i][0]=1;    for(i=n;i>=1;i--)     for(j=i+1;j<=n;j++)    {        if(a[j]>a[i]) f[i][j][1]+=f[i][j-1][0];        if(a[j]>a[j-1]) f[i][j][1]+=f[i][j-1][1];        if(a[i]