题解 P3205 【[HNOI2010]合唱队】

kradcigam

2019-08-28 11:58:32

Solution

### 讲讲我的做法 看了题目发现要用区间 dp,为什么? 我们发现区间 dp 有一个性质——大区间包含小区间,这道题就符合这样的一个性质: ![](https://cdn.luogu.com.cn/upload/pic/75397.png) 所以我们要用区间 dp 来解决这道题。 #### 如何设计状态 那么我们要怎么设计状态,我们想,每给人进入队伍里,只有 2 种可能: 1. 从左边加入; 2. 从右边进入。 所以我们的状态是有3个数: $f_{i,j,0}$ 表示的是第 $i$ 人从左边进来的方案数; $f_{i,j,1}$ 表示的是第 $j$ 人从右边进来的方案数。 #### 推导状态转移方程 从左边进来肯定前 $1$ 个人比他高,前 $1$ 个人有 $2$ 种情况,要么在 $i+1$ 号位置,要么在 $j$ 号位置。 同理, 从右边进来肯定前 $1$ 个人比他矮,前 $1$ 个人有 $2$ 种情况,要么在 $j-1$ 号位置,要么在 $i$ 号位置。 那么状态转移方程就出来了: ```cpp 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$ 的时候显然只有一种方案,所以边界条件是: ```cpp for(int i=1;i<=n;i++)f[i][i][0]=1,f[i][i][1]=1; ``` 然而你会发现你 WA 了,为什么? 因为,只有一个人的时候方案只有 $1$ 种,可是我们这里却有 $2$ 种方案,所以我们得默认 $1$ 个人的时候,是从左边进来,于是我们就有了正确的边界条件: ```cpp for(int i=1;i<=n;i++)f[i][i][0]=1; ``` #### 完整代码 ```cpp #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; } ```