题解 CF1324E 【Sleeping Schedule】
cyh_toby
2020-03-16 09:54:13
# 题意
原题：[CF1324E 【Sleeping Schedule】](https://www.luogu.com.cn/problem/CF1324E)
给定正整数序列 $a$ ，对于每个数可以选择是否 $-1$ ，最终使其前缀和满足：在给定区间 $[l,r]$ 中的出现的值次数最多。
# 分析
不难想到，这种比较关心结果而不关心过程的问题很适合 DP 。
考虑构造状态。
由于涉及到取模等不好处理的运算，状态可以不包含当前的前缀，而只记录位置及使用 $-1$ 操作的次数。也即
$f_{i,j}$ 表示 **处理前 $i$ 个数，使用了 $j$ 次 $-1$ 操作** 的最优解。
那么就需要新开一个变量 $s$ 记录到目前为止的前缀和。可以不开数组，因为 DP 是按顺序进行的。
有点类似于背包问题。
因此状态转移就是
$$f_{i,j}=\bigg((s-j)\text{是否在给定区间中}\bigg)+\max\begin{cases}f_{i-1,j-1}\qquad(\text{在当前位置使用一次操作})\\f_{i-1,j}\qquad(\text{在当前位置不使用操作})\end{cases}$$
此外每次处理 $i$ 的状态时，需要 $s$ 自增 $a_i$ 。
可见是个 $O(n^2)$ 的 DP。
对于判断 $s\!-\!j$ 是否在给定区间中，需要进行一些模处理。具体见代码。
另外，注意 $j$ 的**取值范围**，应该是 $\big[0,i\big]$ 。
有些状态不合法，**要事先初始化为极小值**。
# 源码
```cpp
#include <bits/stdc++.h>
using namespace std;
const int N = 2005;
int n, p, l, r, s;
int f[N][N];
int ans = 0;
int main()
{
memset(f, -0x3f, sizeof(f));
scanf("%d%d%d%d", &n, &p, &l, &r);
f[0][0] = 0;
for (int i = 1; i <= n; i++) {
int x;
scanf("%d", &x);
s = (s+x) % p;
f[i][0] = f[i-1][0] + (l<=s && s<=r);
for (int j = 1; j <= i; j++)
f[i][j] = (l<=((s-j)%p+p)%p && ((s-j)%p+p)%p<=r)+max(f[i-1][j-1], f[i-1][j]);
}
for (int i = 0; i <= n; i++)
ans = max(ans, f[n][i]);
printf("%d", ans);
}
```