题解 P3205 【[HNOI2010]合唱队】

为了在即将到来的晚会上有更好的演出效果，作为 AAA 合唱队负责人的小 A 需要将合唱队的人根据他们的身高排出一个队形。假定合唱队一共 nn 个人，第 ii 个人的身高为 $h_i$ 米（ $1000 le h_i le 2000$ ），并已知任何两个人的身高都不同。假定最终排出的队形是 $A$ 个人站成一排，为了简化问题，小 A 想出了如下排队的方式：他让所有的人先按任意顺序站成一个初始队形，然后从左到右按以下原则依次将每个人插入最终棑排出的队形中：

第一个人直接插入空的当前队形中。

对从第二个人开始的每个人，如果他比前面那个人高（ $h$ 较大），那么将他插入当前队形的最右边。如果他比前面那个人矮（ $h$ 较小），那么将他插入当前队形的最左边。

$n$ 个人全部插入当前队形后便获得最终排出的队形。

如，有 $6$ 个人站成一个初始队形，身高依次为 $1850, 1900, 1700, 1650, 1800,1750$
那么小 A 会按以下步骤获得最终排出的队形：

$1850$ 。

$1850, 1900$ ，因为 $1900 > 1850$ 。

$1700, 1850, 1900$ ，因为 $1700 < 1900$ 。

$1650, 1700, 1850, 1900$ 因为 $1650 < 1700$ 。

$1650, 1700, 1850, 1900, 1800$ ，因为 $1800 > 1650$ 。

$1750, 1650, 1700, 1850, 1900, 1800$ ，因为 $1750 < 1800$ 。

因此，最终排出的队形是 $1750, 1650, 1700, 1850, 1900, 1800$

小 A 心中有一个理想队形，他想知道多少种初始队形可以获得理想的队形。

请求出答案对 $19650827$ 取模的值。

讲讲我的做法

看了题目发现要用区间 $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;
}