HDU 5151《Sit sit sit》是一道经典的区间动态规划（Interval DP）题目，考察了在特定约束条件下，如何计算将一排座位坐满的方案数。

📝 题目描述

有 ( n ) 个座位，编号为 1 至 ( n )，每个座位都有一个颜色。学生依次尝试坐下，若某个座位满足以下三个条件，则该学生无法坐下：

  1. 该座位不是最左或最右的座位；
  2. 该座位的左右两侧都有学生；
  3. 该座位的左右两侧的颜色不同。

求将 ( n ) 个座位全部坐满的方案数。

🧠 思路解析

这道题可以通过区间动态规划来解决。

定义状态

设 dp[i][j] 表示将区间 ([i, j]) 坐满的方案数。

状态转移

对于区间 ([i, j])，我们可以枚举一个位置 ( k ) 作为最后一个坐下的学生的位置。

  • 如果 ( k ) 是最左或最右的座位，则该学生可以坐下，方案数为 dp[i][k-1] * dp[k+1][j]。
  • 如果 ( k ) 的左右两侧都有学生，则需要判断左右两侧的颜色是否相同：
    • 如果相同，则该学生可以坐下，方案数为 dp[i][k-1] * dp[k+1][j]。
    • 如果不同，则该学生无法坐下，方案数为 0。

组合数学

在计算方案数时，需要考虑将学生分配到不同的座位上。

  • 对于一个区间 ([i, j])，可以将其分为两个子区间 ([i, k-1]) 和 ([k+1, j])，其中 ( k ) 是最后一个坐下的学生的位置。
  • 将学生分配到这两个子区间的方式数为组合数 ( C(j-i, k-i) )，即从 ( j-i ) 个座位中选择 ( k-i ) 个座位。

💡 代码实现

以下是使用 C++ 实现的代码示例：

#include <iostream>
#include <vector>
using namespace std;

const int MOD = 1e9 + 7;

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

    vector<vector<long long>> dp(n+1, vector<long long>(n+1, 0));
    vector<vector<long long>> comb(n+1, vector<long long>(n+1, 0));

    for (int i = 0; i <= n; ++i) {
        comb[i][0] = comb[i][i] = 1;
        for (int j = 1; j < i; ++j) {
            comb[i][j] = (comb[i-1][j-1] + comb[i-1][j]) % MOD;
        }
    }

    for (int len = 1; len <= n; ++len) {
        for (int i = 1; i + len - 1 <= n; ++i) {
            int j = i + len - 1;
            if (i == j) {
                dp[i][j] = 1;
            } else {
                for (int k = i; k <= j; ++k) {
                    if (k == i || k == j || color[k-1] == color[k+1]) {
                        dp[i][j] = (dp[i][j] + dp[i][k-1] * dp[k+1][j] % MOD * comb[j-i][k-i]) % MOD;
                    }
                }
            }
        }
    }

    cout << dp[1][n] << endl;
    return 0;
}

📚 参考资料