【BZOJ1996】[Hnoi2010]chorus 合唱队 区间DP

【BZOJ1996】[Hnoi2010]chorus 合唱队

Description

Input

Output

Sample Input

4
1701 1702 1703 1704

Sample Output

8

HINT

题解：用f[i][j][0/1]表示从i开始往后j个人，最后一个人是i/i+j-1，的方案数。$O(n^2)$DP即可。

#include <cstdio>

#include <cstring>

#include <iostream>

using namespace std;

const int P=19650827;

int n;

int f[1010][1010][2],v[1010];

int main()

{

	scanf("%d",&n);

	int i,j;

	for(i=1;i<=n;i++)	scanf("%d",&v[i]),f[0][i][0]=1;

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

	{

		for(j=1;j<=n-i;j++)

		{

			if(v[j]<v[j+1])	f[i][j][0]=(f[i][j][0]+f[i-1][j+1][0])%P;

			if(v[j]<v[j+i])	f[i][j][0]=(f[i][j][0]+f[i-1][j+1][1])%P;

			if(v[j+i]>v[j])	f[i][j][1]=(f[i][j][1]+f[i-1][j][0])%P;

			if(v[j+i]>v[j+i-1])	f[i][j][1]=(f[i][j][1]+f[i-1][j][1])%P;

		}

	}

	printf("%d",(f[n-1][1][0]+f[n-1][1][1])%P);

	return 0;

}