bzoj1996 [Hnoi2010]chorus 合唱队

Description

Input

Output

Sample Input

4
1701 1702 1703 1704

Sample Output

8

HINT

一开始我也是没什么思路的……

随便写了几个数据画了画，结果发现其实每次新加入一个数的时候都是把当前的数列向左或者向右拓展一位

意思就是每次都是在一个区间上往两边加数。然后很显然区间dp啦

结合数据范围就更显然了

后来发现用二维的统计好像是有问题的，要三维

f[i][j][0/1]表示取到数列中从i到j的区间，上一个取到的是数列左边/右边的数

f[i][j][0]=f[i+1][j][0]*(a[i]<a[i+1])+f[i+1][j][1]*(a[i]<a[j])

f[i][j][1]=f[i][j+1][0]*(a[j]>a[i])+f[i][j+1][1]*(a[j]>a[j-1])

#include<cstdio>
#define mod 19650827
inline int read()
{
    int x=0,f=1;char ch=getchar();
    while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
    while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
    return x*f;
}
int n;
int a[1010];
int f[1010][1010][2];
int main()
{
	n=read();
	for (int i=1;i<=n;i++)a[i]=read();
	for (int i=1;i<=n;i++)f[i][i][0]=1;
	for (int i=n;i>=1;i--)
	for (int j=i+1;j<=n;j++)
	{
		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[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];
		f[i][j][0]%=mod;
		f[i][j][1]%=mod;
	}
	printf("%d
",(f[1][n][0]+f[1][n][1])%mod);
}