题解 P3205 【[HNOI2010]合唱队】

讲讲我的做法

看了题目发现要用区间\(dp\)，为什么?

我们发现区间\(dp\)有一个性质——大区间包涵小区间，这道题就符合这样的一个性质



所以我们要用区间\(dp\)来解决这道题。

如何设计状态

那么我们要怎么设计状态，我们想，每给人进入队伍里，只有2种可能，1种是从左边加入，另外1种是从右边进入，所以我们的装态是有3个数

\(f[i][j][0]\)表示的是第\(i\)人从左边进来的方案数

\(f[i][j][1]\)表示的是第\(j\)人从右边进来的方案数

推导状态转移方程

从左边进来肯定前1个人比他高，前1个人有2种情况，要么在\(i+1\)号位置，要么在\(j\)号位置。

同理

从右边进来肯定前1个人比他矮，前1个人有2种情况，要么在\(j-1\)号位置，要么在\(i\)号位置。

那么状态转移方程就出来了

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]%=19650827;

f[i][j][1]%=19650827;

边界条件

当\(i=j\)的时候显然只有一种方案，所以边界条件是

for(int i=1;i<=n;i++)f[i][i][0]=1,f[i][i][1]=1;

然而你会发现你WA了，为什么

因为，只有一个人的时候方案只有一种，可是我们这里却有2种方案，所以我们得默认1个人的时候，是从左边进来，于是我们就有了正确的边界条件

for(int i=1;i<=n;i++)f[i][i][0]=1;

完整代码

#include <bits/stdc++.h>

using namespace std;

int f[2010][2010][2],a[2010];

int main(){

	int n;

	cin>>n;

	for(int i=1;i<=n;i++)cin>>a[i];

	for(int i=1;i<=n;i++)f[i][i][0]=1;

	for(int len=1;len<=n;len++)

		for(int i=1,j=i+len;j<=n;i++,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]%=19650827;

			f[i][j][1]%=19650827;

		}

	cout<<(f[1][n][0]+f[1][n][1])%19650827;

	return 0;

}