您现在的位置：程式碼之家 >> 編程語言 > >> C語言 >> C++ >> 關於C++

BZOJ 1996 [HNOI2010] Chorus 合唱隊 —— 區間 DP 計數合法排列數

編輯：關於C++

BZOJ 1996：N ≤ 2000 位學生身高已知，從中選若干人排成一排，要求：從左到右先嚴格增高再嚴格降低（山形），或全增/全降。求合法排列方案數模 19650827。等價於：對給定序列，計算有多少子序列是「先嚴格遞增後嚴格遞減」（允許峰值在兩端）。

一、DP 狀態定義

f[i][j][0/1]：區間 [i, j] 內合法排列數，其中 最後加入的人 分別是 i（左端）或 j（右端）。

0：最後加入的是 i（當前最矮在左）
1：最後加入的是 j（當前最矮在右）

遞推時從小區間向大區間擴展，保證「最矮」逐步加入。

二、遞推方程

區間長度 len = j-i+1。考慮將 i 或 j 作為「最矮」加入：

// 初始化
for (int i = 1; i <= n; ++i) f[i][i][0] = f[i][i][1] = 1;

// 長度 2 特判
if (i+1 == j) {
    if (a[i] < a[j]) { f[i][j][0] = 1; f[i][j][1] = 1; }
    else if (a[i] > a[j]) { f[i][j][0] = 1; f[i][j][1] = 1; }
    // 相等不合法，但題目保證身高互不相同
}

// 一般情況 len >= 3
// 最後加入 i（最矮在左）
if (a[i] < a[i+1]) f[i][j][0] = (f[i][j][0] + f[i+1][j][0]) % mod;
if (a[i] < a[j])   f[i][j][0] = (f[i][j][0] + f[i+1][j][1]) % mod;

// 最後加入 j（最矮在右）
if (a[j] < a[i])   f[i][j][1] = (f[i][j][1] + f[i][j-1][0]) % mod;
if (a[j] < a[j-1]) f[i][j][1] = (f[i][j][1] + f[i][j-1][1]) % mod;

三、最終答案

ans = (f[1][n][0] + f[1][n][1]) % mod

四、完整 AC 代碼

#include <bits/stdc++.h>
using namespace std;
const int MAXN = 2005;
const int MOD = 19650827;
int n, a[MAXN], f[MAXN][MAXN][2];

int main() {
    scanf("%d", &n);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    memset(f, 0, sizeof(f));
    for (int i = 1; i <= n; ++i) f[i][i][0] = f[i][i][1] = 1;
    for (int len = 2; len <= n; ++len) {
        for (int i = 1; i+len-1 <= n; ++i) {
            int j = i+len-1;
            if (len == 2) {
                if (a[i] < a[j]) f[i][j][0] = f[i][j][1] = 1;
                else f[i][j][0] = f[i][j][1] = 1;
                continue;
            }
            if (a[i] < a[i+1]) f[i][j][0] = (f[i][j][0] + f[i+1][j][0]) % MOD;
            if (a[i] < a[j])   f[i][j][0] = (f[i][j][0] + f[i+1][j][1]) % MOD;
            if (a[j] < a[i])   f[i][j][1] = (f[i][j][1] + f[i][j-1][0]) % MOD;
            if (a[j] < a[j-1]) f[i][j][1] = (f[i][j][1] + f[i][j-1][1]) % MOD;
        }
    }
    printf("%d\n", (f[1][n][0] + f[1][n][1]) % MOD);
    return 0;
}