Codeforces 1324 E. Sleeping Schedule（DP）

题意：nnn 个时间间隔，一天共有 hhh 小时，每次睡 aia_iai 或者 ai−1a_{i-1}ai−1 段时间，如果在 lll 和 rrr 段时间入睡那么满意度 +1+1+1 ,问满意度最高多少用 dp[i][j]dp[i][j]dp[i][j] 表示在第 iii 段在第 jjj 小时睡觉的最大满意值。然后直接 dpdpdp 即可。AC代码：const int N = 2...

邵光亮

149111人浏览 · 2020-03-14 08:33:03

邵光亮 · 2020-03-14 08:33:03 发布

在这里插入图片描述

题意：

$n$ 个时间间隔，一天共有 $h$ 小时，每次睡 $a_i$ 或者 $a_{i-1}$ 段时间，如果在 $l$ 和 $r$ 段时间入睡那么满意度 $+ 1$ ,问满意度最高多少

用 $d p [i] [j]$ 表示在第 $i$ 段在第 $j$ 小时睡觉的最大满意值。然后直接 $d p$ 即可。

AC代码：

const int N = 2000 + 10;
int n, m, h, l, r;
int ans, res, cnt, pos;
int a[N];
int dp[N][N];
int main()
{
    sdd(n, h);
    sdd(l, r);
    mem(dp, -0x3f);
    rep(i, 1, n)
        sd(a[i]);
    dp[0][0] = 0;
    rep(i, 1, n)
    {
        rep(j, 0, h - 1)
        {
            dp[i][j] = max(dp[i - 1][(j - a[i] + h) % h], dp[i - 1][(j - (a[i]-1) + h) % h]) + (l <= j && j <= r);
        }
    }
    ans = 0;
    rep(i, 0, h - 1)
        ans = max(dp[n][i], ans);
    pd(ans);
    return 0;
}