luogu3205 [HNOI2010]CHORUS 合唱队

luogu题面炸了，可以去bzoj1996看题面

题目描述

输入

输出

样例输入

4

1701 1702 1703 1704

样例输出

8

提示

题解

这是什么DP呢？发现好像加完后区间里面的数值就和没啥关系了，只和第一个数值有关。

这种枚举区间的应该就是区间dp了吧。。

$f[i][j][k]$表示区间$i-j$最后一个放的是$i/j,(k=0/1)$的方案数。

然后枚举就好了，注意要枚举区间长度，才能往下推。

还有$f[i][i][0]=1,f[i][i][1]=0$，如果都是1，就会算重。

#include <cstdio>
#include <algorithm>
#define N 1010
#define mod 19650827
using namespace std;
int n,a[N],f[N][N][2];
main()
{
    scanf("%d",&n);
    for (int i=1;i<=n;i++)
        scanf("%d",&a[i]);
    for (int i=1;i<=n;i++)
        f[i][i][0]=1;
    for (int k=1;k<n;k++)
        for (int i=1;i+k<=n;i++)
        {
            int j=i+k;
            if (a[i]<a[i+1])f[i][j][0]+=f[i+1][j][0];
            if (a[i]<a[j])  f[i][j][0]+=f[i+1][j][1];
            if (a[j]>a[j-1])f[i][j][1]+=f[i][j-1][1];
            if (a[j]>a[i])  f[i][j][1]+=f[i][j-1][0];
            f[i][j][0]%=mod,f[i][j][1]%=mod;
        }
    printf("%d",(f[1][n][0]+f[1][n][1])%mod);
}