ZHK

ZHK

一只叫ZHK的蒟蒻为了RP而战

题解 P3205 【[HNOI2010]合唱队】

posted on 2019-08-28 11:58:32 | under 题解 |

讲讲我的做法

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