洛谷题单指南-动态规划3-P3205 [HNOI2010] 合唱队

原题链接：https://www.luogu.com.cn/problem/P3205

题意解读：给定理想队形，计算初始队形的方案数。

解题思路：

对于给定理想队形，最后一个人插入有两种可能：从左边插入、从右边插入

从左边插入，则意味着前一个数比当前数大，前一个数有可能在左边也有可能在右边

从右边插入，则意味着前一个数比当前数小，前一个数有可能在左边也有可能在右边

根据上述分析，可以这样来设计：

1、状态表示

设f[i][j]表示形成i~j的理想队形，最后一个插入的是i，对应从左边插入的情况

设g[i][j]表示形成i~j的理想队形，最后一个插入的是j，对应从右边插入的情况

理想队形第i个人身高h[i]。

2、状态转移

如果最后一个i从左边插入，那么前一个数大于h[i]，前一个数可能是h[i+1]或者h[j]

  当h[i+1] > h[i]，f[i][j] += f[i+1][j]，f[i][j]加上i+1~j从左边插入的方案数

  当h[j] > h[i]，f[i][j] += g[i+1][j]，f[i][j]加上i+1~j从右边插入的方案数

如果最后一个j从右边插入，那么前一个数小于h[j]，前一个数可能是h[i]或者h[j-1]

  当h[i] < h[j]，g[i][j] += f[i][j-1]，g[i][j]加上i~j-1从左边插入的方案数

  当h[j-1] < h[j]，g[i][j] += g[i][j-1]，g[i][j]加上i~j-1从右边插入的方案数

3、初始化

对于i=j的情况，将f[i][j]或者g[i][j]置为1即可，注意不能都置1，因为只有一个数，对应一种方案，要么认为左边插入、要么认为左边插入

4、结果

f[1][n] + g[1][n]

5、遍历方式，同常规区间问题，先枚举长度，再枚举左边界，计算右边界

6、注意每一步计算，要对f、g取模

100分代码：

#include <bits/stdc++.h>
using namespace std;

const int N = 1005, MOD = 19650827;
int n;
int h[N];
int f[N][N]; //f[i][j]表示形成i~j的理想队形，最后一个插入的是i，对应从左边插入的情况
int g[N][N]; //g[i][j]表示形成i~j的理想队形，最后一个插入的是j，对应从右边插入的情况

int main()
{
    cin >> n;
    for(int i = 1; i <= n; i++)
    {
        cin >> h[i];
        f[i][i] = 1;
    } 

    for(int len = 2; len <= n; len++)
    {
        for(int i = 1; i + len - 1 <= n; i++)
        {
            int j = i + len - 1;
            if(h[i+1] > h[i]) f[i][j] += f[i+1][j];
            if(h[j] > h[i]) f[i][j] += g[i+1][j];
            if(h[i] < h[j]) g[i][j] += f[i][j-1];
            if(h[j-1] < h[j]) g[i][j] += g[i][j-1];
            f[i][j] %= MOD;
            g[i][j] %= MOD;
        }
    }
    cout << (f[1][n] + g[1][n]) % MOD;

    return 0;
}