【题解】[HNOI2010]合唱队

题目戳我

( ext{Solution:})

设(dp[l][r][0/1])表示区间([l,r])已经排列好，且这个人是从左边/右边加入进来的。

考虑分别转移：

(dp[l][r][0]=[a_l<a_{l+1}]dp[l+1][r][0]+[a_l<a_r]dp[l+1][r][1])

(dp[l][r][1]=[a_r>a_l]dp[l][r-1][0]+[a_r>a_{r-1}]dp[l][r-1][1])

大概就是根据题目，对第一个方程进行解释：

若区间([l+1,r])已经排列好的且最后一个人是从左边进来的（(dp[l+1][r][0])）,这时我们要求当前人从左边进来((dp[l][r][0])),那么必须满足(a_l<a_{l-1}.)

后面方程同理。

考虑初始条件：原来的是(dp[i][i][0]=dp[i][i][1]=1,)这时会发现，原本只有一个人，方案数应该是(1,)此时却是两种。于是，我们强行规定一个人的时候是从左边进入的，就可以正确得到初始条件：(dp[i][i][0]=1.)

#include<bits/stdc++.h>
using namespace std;
const int mod=19650827;
inline int add(int x,int y){return (x+y)%mod;}
const int MAXN=2010;
int dp[MAXN][MAXN][2],a[MAXN],n,ans;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;++i)scanf("%d",a+i);
	for(int i=1;i<=n;++i)dp[i][i][0]=1;
	for(int len=1;len<=n;++len){
		for(int l=1,r=l+len;r<=n;l++,r++){
			dp[l][r][0]=add(dp[l+1][r][0]*(a[l]<a[l+1]),dp[l+1][r][1]*(a[l]<a[r]));
			dp[l][r][1]=add(dp[l][r-1][0]*(a[r]>a[l]),dp[l][r-1][1]*(a[r]>a[r-1]));
		}
	}
	ans=add(dp[1][n][1],dp[1][n][0]);
	printf("%d
",ans);
	return 0;
}