CodeForces-1324E Sleeping Schedule

Table of Contents

CodeForces-1324E Sleeping Schedule #

题目大意 #

给定 $h, l, r$ 和长度为 $n$ 的数组 $a$ . 对于每个 $a_i$ , 你可以用 $a_i - 1$ 替换它. 记 $s$ 为经过操作的 $a$ 的前缀和数组, 如果 $l\leq (s_i% h)\leq r$ , 就得到一分. 求总得分的最大值.

Solution 1 #

用 $dp[i][j]$ 表示 $a_0, …, a_i$ 中有 $j$ 个数被替换时的最大得分. 动态规划即可. 代码如下:

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

int main() {
    int n, h, l, r;
    cin >> n >> h >> l >> r;
    int a[n];
    for (int i = 0; i < n; i++) {
        cin >> a[i];
        if (i > 0) {
            a[i] += a[i - 1];
        }
    }
    vector<vector<int>> dp(n, vector<int>(n + 1, 0));
    dp[0][0] = (l <= a[0] % h) && (r >= a[0] % h);
    dp[0][1] = (l <= (a[0] - 1) % h) && (r >= (a[0] - 1) % h);
    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= i + 1; j++) {
            dp[i][j] =
                ((l <= (a[i] - j) % h) && (r >= (a[i] - j) % h)) +
                (j > 0 ? max(dp[i - 1][j - 1], dp[i - 1][j]) : dp[i - 1][j]);
        }
    }
    int ans = 0;
    for (int j = 0; j <= n; j++) {
        ans = max(ans, dp[n - 1][j]);
    }
    cout << ans << endl;
    return 0;
}