【区间dp】洛谷 P3205 [HNOI2010]合唱队

P3205 [HNOI2010]合唱队 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)

题意：有一个初始队形，这个初始队形可以是任意队形

给定一个理想队形，问你通过以下的排列方式有几种方案数可以使初始队形变成理想队形

排列方式是这样的：一开始队列里是初始队列中的第一个人，然后继续按顺序把初始队列中的人放入队列中，如果这个人比上一轮选的人要高，就放在队列最右边，否则放最左边

思路：

这道题以1~n的区间作为主体，因此是个区间dp

那么首先我们先去设状态

设状态需要考虑主体的属性和决策，这道题主体的属性就是方案数

因为这是区间dp，我们先设状态为f[i][j]，表示理想队形[i,j]可以由f[i][j]种初始队列转化而来

题目的决策是把数字放队列最左边或最右边，因此我们把状态增加一维

设f[i][j][0]表示理想队形[i,j]可以由f[i][j][0]种初始队列转化而来，其中最后一个决策是把数字放队列最左边

类似地，设f[i][j][1]表示理想队形[i,j]可以由f[i][j][1]种初始队列转化而来，其中最后一个决策是把数字放队列最右边

设完状态后，我们去转移状态

转移状态时我们考虑造成该状态的最后一步决策

这一步因为大小关系我们把数放最左边，上一步的最后一步可能是放最左边，也可能是放最右边

如果上一步的最后一步放左边，那么就把上一步在执行的数和这一步在执行的数进行比较，以此类推，具体看代码：

f[l][r][0]+=(f[l+1][r][0]%mod*(a[l+1]>a[l])+f[l+1][r][1]%mod*(a[r]>a[l]))%mod;
f[l][r][1]+=(f[l][r-1][0]%mod*(a[r]>a[l])+f[l][r-1][1]%mod*(a[r]>a[r-1]))%mod;

那第一个式子为例，f[l][r][0]的含义是区间[l，r]是由f[l][r][0]种初始区间转化而来，其中最后一步是把数字放最左边

那么分类讨论，比较a[l]和a[l+1]的大小，如果小于就是这一步的最后一个决策是把放最左边，上一步的决策是把数字放最左边时，同理，比较a[r]和a[l]的大小，然后a[r]>a[l]，那么就是这一步把数字放最左边，上一步把数字放最右边，其余以此类推即可

状态转移完后，去初始化

显然，f[i][i][0]=f[i][i][1]=1

然而，这样初始化是错的，因为这样表示只有一个数时有从左插和从右插两种方案，但是这两种方案在现实中说等价的，因此我们就默认第一次插是从左插的就好了，当然，也可以默认第一次是从右插的。

所以，在初始化的时候，我们要考虑初始化的现实意义

Code：

#include <bits/stdc++.h>
using namespace std;
const int mxn=1e3+10,mod=19650827;
int n;
int a[mxn],f[mxn][mxn][2];
int main(){
    scanf("%d",&n);
    memset(f,0,sizeof(f));
    for(int i=1;i<=n;i++) f[i][i][0]=1;
    for(int i=1;i<=n;i++) scanf("%d",&a[i]);
    for(int i=1;i<n;i++){
        for(int j=1;j<=n-i;j++){
            int l=j,r=j+i;
            f[l][r][0]=(f[l+1][r][0]%mod*(a[l+1]>a[l])+f[l+1][r][1]%mod*(a[r]>a[l]))%mod;
            f[l][r][1]=(f[l][r-1][0]%mod*(a[r]>a[l])+f[l][r-1][1]%mod*(a[r]>a[r-1]))%mod;
        }
    }
    /*for(int i=1;i<=n-1;i++){
        for(int j=i+1;j<=n;j++){
            printf("[%d,%d]:%d %d\n",i,j,f[i][j][0],f[i][j][1]);
        }
    }*/
    printf("%d\n",(f[1][n][0]%mod+f[1][n][1]%mod)%mod);
    return 0;
}

总结：

1.在初始化的时候，我们要考虑初始化的现实意义

2.设状态需要考虑主体的属性和决策，这道题主体的属性就是方案数

3.转移状态时我们考虑造成该状态的最后一步决策