ALGORITHM NOTES阅读地图
8个主要章节
1段代码示例
4组图片与图表

先明确状态与不变量,再对照手算、证明、边界和实现。

章节速览8 节 · 展开选择

前缀和能快速求区间收益,基础DP要求分清不可达与零收益。这次把两者结合:难点不是求区间和,而是表达“前缀里恰好选了几个区间”。

Codeforces 467C:George and Job要求恰好选k个长度m、互不相交的连续区间,使总和最大。官方难度1700,标签dp、implementation。约束1≤mk≤n≤5000,0≤pᵢ≤10⁹。本文使用1起点闭区间,相邻但不共享位置的两段可以同时选。

单个窗口最强,为何整体却失败

取p=[5,6,6,5,0,0],m=2,k=2。单个最大窗口[2,3]收益12;选它后,剩下可用的窗口最好是[5,6],收益0,总计12。但[1,2]与[3,4]各得11,合计22。局部选择同时阻挡两个稍弱窗口,非负收益也不能消除位置冲突。

枚举k个窗口会产生组合规模的搜索。我们需要利用位置顺序,把已经处理的前缀压缩成少量信息。这里“选了几段”影响未来还须选多少段,不能从状态中省掉。

在5、6、6、5、0、0中,中间窗口12阻挡两个11分窗口,最优总分22
位置冲突使最大窗口贪心失效

教学反例,m=2、k=2;横线标记位置范围,不是收益比例。

查看原图

先定义前缀与恰好数量

令S[0]=0、S[i]=p₁+…+pᵢ。以i结尾的定长区间[i−m+1,i],收益为S[i]−S[i−m]。注意减去的是左端点之前的前缀。

令F[t][i]表示仅使用前i个位置、恰好选择t段的最大收益。F[0][i]=0;i<tm时位置不足,状态不可达,记作负无穷,不能当作合法零收益。最终答案为F[k][n]。

转移J1:最后位置的两种归属

F[t][i] = max(F[t][i−1], F[t−1][i−m] + S[i] − S[i−m])。

条件:t≥1,第二项须i≥m且前驱可达;收益单位为题目的分数。

若不用位置i,继承较短前缀。若使用i,由于它是前缀最后位置,最后一段只能结束于i,长度固定便唯一确定其左端点;其余t−1段必须全部在前i−m个位置。

不能用F[t−1][i−1]接窗口:这个前驱可能已经占用了新窗口内部的位置。也不能只保留一个不带t的前缀最优值,那会混淆不同的区间数量。

完备性与合法性证明

任意合法最优解要么不用i,要么用i。前者属于第一项;后者移除最后一段后,必得到第二项的合法前驱,两类覆盖全部解。反过来,第一项保持合法;第二项连接的前驱与新段位置不相交,数量恰好增加1,所以能构造出合法方案。

以t递增、每层i递增计算,所需前驱都已经确定。从边界状态归纳,J1便得到正确最优值。本题只求最大值,多个等值方案不必去重;若改为统计方案数,需要重新设计等值合并规则。

逐格手算反例

前缀和为0、5、11、17、22、22、22。

段数与前缀 0 1 2 3 4 5 6
0 0 0 0 0 0 0 0
1 不可达 不可达 11 12 12 12 12
2 不可达 不可达 不可达 不可达 22 22 22

关键格F[2][4]=F[1][2]+S[4]−S[2]=11+11=22。它接入的是受位置边界约束的前驱11,而不是任意位置上的单窗口最高收益12。F[2][6]还允许最后位置不被选择,继承项已经保留这种可能。

两行滚动必须保持层的身份

当前层依赖当前层左侧和上一层i−m。prev始终表示恰好t−1段,cur表示恰好t段;每轮将cur重置为不可达,整层完成后才交换。原地从左向右写,可能把当前层刚产生的结果误作上一层,m=1时尤其容易反复接入。

完整C++17与复杂度

程序按官方输入契约工作,不实现非法输入恢复。前缀和及答案至多5×10¹²,使用long long。NEG仅表示不可达,相加前先检查,避免把哨兵用于普通算术。时间O(nk),额外空间O(n),包含前缀数组;最坏约2500万次状态访问。这里只输出最优值,还原具体窗口需要另存决策或设计重算。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
#include <algorithm>
#include <iostream>
#include <limits>
#include <vector>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, m, k;
if (!(cin >> n >> m >> k)) return 0;
vector<long long> s(n + 1, 0);
for (int i = 1; i <= n; ++i) {
long long x;
cin >> x;
s[i] = s[i - 1] + x;
}
const long long NEG = numeric_limits<long long>::lowest() / 4;
vector<long long> prev(n + 1, 0), cur(n + 1, NEG);
for (int t = 1; t <= k; ++t) {
fill(cur.begin(), cur.end(), NEG);
for (int i = 1; i <= n; ++i) {
cur[i] = cur[i - 1];
if (i >= m && prev[i - m] != NEG)
cur[i] = max(cur[i], prev[i - m] + s[i] - s[i - m]);
}
prev.swap(cur);
}
cout << prev[n] << '\n';
}

边界与自检

m=1时答案等于最大的k个元素之和;mk=n时所有位置必须选中;k=1时等于最大定长窗口和。这些退化情形提供独立参考。全零时答案为0,但位置不足仍不可达。

[1,2]与[3,4]能同时选吗?

可以。闭区间不共享位置,相邻不等于重叠。

收益非负,是否意味着状态可以全初始化为0?

某些变形可能借助非负性得到相同最终值,但已不能保持本文“恰好t段”的状态解释。不可达哨兵让证明与调试一致,不能把位置不足称为合法零收益方案。

来源与衔接

  1. Codeforces官方题页:题目契约、范围、样例与标签;证明、图与反例为原创。
  2. 474D计数DP:继续比较最优值与方案数两种不同的合并方式。