五、排队形

题目描述

为了在即将到来的晚会上有更好的演出效果，作为 AAA 合唱队负责人的小 A 需要将合唱队的人根据他们的身高排出一个队形。假定合唱队一共 n 个人， 第 i 个人的身高为 h 米（1000≤hi≤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 取模的值。

输入描述

第一行一个整数 n 第二行 n 个整数，表示小 A 心中的理想队形。

输出描述

输出一行一个整数，表示答案 mod19650827 的值。 输入输出样例：

输入：

4
1701 1702 1703 1704

输出：

8

说明/提示

对于 30% 的数据，n≤100。 对于 100% 的数据，n≤1000，1000≤hi ≤2000。

视频题解

https://dl.ccf.org.cn/video/videoDetail.html?_ack=1&id=7092424602028032

C++ 实现与解释

  1. 动态规划表：dp[l][r] 表示从第 l 到第 r 个人的子序列可以通过多少种初始队形生成。
  2. 状态转移：
    • 如果第 l 个人是最后一个被插入的，那么他必须比第 l+1 个人矮，即 h[l] < h[l+1]。
    • 如果第 r 个人是最后一个被插入的，那么他必须比第 r-1 个人高，即 h[r] > h[r-1]。
  3. 边界条件：当 l == r 时，dp[l][r] = 1，因为只有一个人时，初始队形只有一种。
  4. 最终答案：dp[1][n] 即为所求的初始队形数量，最后对 19650827 取模。
#include <iostream>
#include <vector>

using namespace std;

const int MOD = 19650827;
const int MAXN = 1000;  // 假设最大人数为 1000
int h[MAXN];            // 全局数组存储身高
int dp[MAXN][MAXN];     // 全局动态规划表

int fn(int n) {
    for (int l = n; l >= 1; --l) {
        for (int r = l; r <= n; ++r) {
            if (l == r) {
                dp[l][r] = 1;
            } else {
                if (l + 1 <= n && h[l] < h[l + 1]) {
                    dp[l][r] = (dp[l][r] + dp[l + 1][r]) % MOD;
                }
                if (r - 1 >= 1 && h[r] > h[r - 1]) {
                    dp[l][r] = (dp[l][r] + dp[l][r - 1]) % MOD;
                }
            }
        }
    }

    return dp[1][n];
}

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

    cout << fn(n) << endl;  // 输出：8

    return 0;
}