Codeforces Round #627 (Div. 3) E. Sleeping Schedule 线性DP

墨蓝 2023-07-15 13:02 30阅读 0赞

题目链接：[http://codeforces.com/contest/1324/problem/E][http_codeforces.com_contest_1324_problem_E]

题意：每天有h小时，总共要睡n次，每次你可以选择在a\[i\] or a\[i\] - 1小时后睡觉。如果睡觉的区间在\[l, r\]的话认为是好的

求如何安排使得睡觉好的次数最多。

思路：f\[i\]\[j\] 表示第i次在时间j睡觉的最多次数，有点类似背包的思想，我们枚举时间，每次只需要判断当前时间是否在\[l, r\]中

目标状态max(f\[n\]\[k\])  0 <= k < h

#include<bits/stdc++.h>
    using namespace std;
    typedef long long ll;
    #define ls rt << 1
    #define rs rt << 1|1
    #define lson l, mid, ls
    #define rson mid + 1, r, rs
    const int maxn = 3e3 + 10;
    const int inf = 0x3f3f3f3f;
    int a[maxn], f[maxn][maxn];
    
    int main()
    {
        memset(f, -1, sizeof(f));
        int n, h, l, r;
        scanf("%d%d%d%d", &n, &h, &l, &r);
        for(int i = 1; i <= n; ++i) scanf("%d", &a[i]);
        f[0][0] = 0;
        for(int i = 1; i <= n; ++i)
        {
            for(int j = 0; j < h; ++j)
            {
                int x = (j + a[i]) % h, y = (j + a[i] - 1 + h) % h;
                if(f[i - 1][j] != -1)
                {
                    if(x >= l && x <= r) f[i][x] = max(f[i][x], f[i - 1][j] + 1);
                    else f[i][x] = max(f[i][x], f[i - 1][j]);
                    if(y >= l && y <= r) f[i][y] = max(f[i][y], f[i - 1][j] + 1);
                    else f[i][y] = max(f[i][y], f[i - 1][j]);
                }
            }
        }
        int ans = 0;
        for(int i = 0; i < h; ++i) ans = max(ans, f[n][i]);
        printf("%d\n", ans);
        return 0;
    }

[http_codeforces.com_contest_1324_problem_E]: http://codeforces.com/contest/1324/problem/E