[HNOI2010]合唱队

洛咕

分析:根据它放人的规则,合唱队形从安排第一个人开始一定都会是一段连续的区间,所以考虑区间\(DP\).设\(f[i][j]\)表示安排好理想队形的\([i,j]\)时的方案数.

但是发现转移的时候需要知道上一次放的是哪一个数,所以拓展一维状态\(f[i][j][0/1]\)表示安排好理想队形的\([i,j]\)且当前放\(a_i/a_j\)时的方案数.

转移就不写了.

#include
#include
#include
#include
#include
#include
#include
#include
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int mod=19650827;
const int N=1005;
int a[N];ll f[N][N][2];
int main(){
	int n=read();
	for(int i=1;i<=n;++i)a[i]=read();
	for(int i=1;i<=n;++i){
		f[i][i][0]=f[i][i][1]=1;
		f[i][i+1][0]=(a[i]a[i]);
	}
	for(int len=3;len<=n;++len){
		for(int i=1;i+len-1<=n;++i){
			int j=i+len-1;
			if(a[i]a[i])f[i][j][1]=(f[i][j][1]+f[i][j-1][0])%mod;
			if(a[j]>a[j-1])f[i][j][1]=(f[i][j][1]+f[i][j-1][1])%mod;
		}
	}
	printf("%lld\n",(f[1][n][0]+f[1][n][1])%mod);
	return 0;
}
动态规划-区间DP

相关

标签