解题思路 这道题的核心是通过放置床垫来阻止造反的连锁反应，从而使在时间 T 及以前造反的罪犯数量最少。关键在于理解床垫的作用：在牢房 i 和 i+1 之间放置床垫后，i 的造反不会影响 i+1 的原定造反时间。 我们可以使用动态规划来解决这个问题： 定义dp[i][j]表示考虑前 i 个牢房，使用 j 个床垫时，第 i 个牢房的造反时间 对于每个牢房 i 和床垫数量 j，有两种选择： 不在 i-1 和 i 之间放床垫：则 i 的造反时间是dp[i-1][j] + 1 在 i-1 和 i 之间放床垫：则 i 的造反时间是其原定时间t[i]（需 j>0） 我们选择两种方案中较大的时间（这样能减少造反的可能性） 最后统计所有造反时间≤T 的牢房数量 C++ 代码实现 cpp 运行 #include <bits/stdc++.h> using namespace std;

int main() { ios::sync_with_stdio(false); cin.tie(nullptr);

int N, D, T;
cin >> N >> D >> T;

vector<int> t(N + 1);  // 1-based indexing
for (int i = 1; i <= N; ++i) {
    cin >> t[i];
}

// dp[i][j]表示前i个牢房使用j个床垫时，第i个牢房的造反时间
// 为节省空间，使用滚动数组
vector<vector<int>> dp(2, vector<int>(D + 1));

// 初始化第一个牢房
dp[1][0] = t[1];
for (int j = 1; j <= D; ++j) {
    dp[1][j] = t[1];  // 第一个牢房前不能放床垫，所以值不变
}

for (int i = 2; i <= N; ++i) {
    int curr = i % 2;
    int prev = 1 - curr;
    
    // 不使用新床垫
    dp[curr][0] = dp[prev][0] + 1;
    
    // 使用新床垫（j从1到D）
    for (int j = 1; j <= D; ++j) {
        // 两种选择：不在i-1和i间放床垫 或 放床垫
        dp[curr][j] = max(dp[prev][j] + 1, t[i]);
    }
}

// 统计造反时间<=T的牢房数量
int last = N % 2;
int count = 0;
for (int i = 1; i <= N; ++i) {
    int curr = i % 2;
    if (dp[curr][D] <= T) {
        count++;
    }
}

cout << count << endl;

return 0;

} 代码解释 数据结构：使用滚动数组dp[2][D+1]来优化空间，因为计算第 i 个牢房时只需要第 i-1 个牢房的信息。 动态规划转移： 对于每个牢房 i 和床垫数量 j，我们选择两种方案中造反时间较晚的那个 这样做的目的是尽量让造反时间超过 T，从而减少造反的牢房数量 空间优化：通过滚动数组将空间复杂度从 O (N×D) 降低到 O (D)，使其能处理 N=2×10^6 的情况 时间复杂度：O (N×D)，其中 N 是牢房数量，D 是床垫数量 这个解法高效地计算出了在最优放置床垫的情况下，在时间 T 及以前造反的最少罪犯数量。