Codeforces 467C 从定长区间到恰好选择的前缀DP
先明确状态与不变量,再对照手算、证明、边界和实现。
章节速览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个窗口会产生组合规模的搜索。我们需要利用位置顺序,把已经处理的前缀压缩成少量信息。这里“选了几段”影响未来还须选多少段,不能从状态中省掉。
教学反例,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]。
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的前缀最优值,那会混淆不同的区间数量。
flowchart TD
A[前缀恰好选择若干段] --> B{使用最后位置}
B -->|否| C[继承较短前缀]
B -->|是| D[最后一段唯一确定]
D --> E[接入该段之前的上一层]
C --> F[取合法收益最大值]
E --> F
完备性与合法性证明
任意合法最优解要么不用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时尤其容易反复接入。
flowchart TD A[上一层保持只读] --> B[当前层重置] B --> C[从左到右计算] C --> D[整层完成后交换] D --> E[进入下一个段数]
完整C++17与复杂度
程序按官方输入契约工作,不实现非法输入恢复。前缀和及答案至多5×10¹²,使用long long。NEG仅表示不可达,相加前先检查,避免把哨兵用于普通算术。时间O(nk),额外空间O(n),包含前缀数组;最坏约2500万次状态访问。这里只输出最优值,还原具体窗口需要另存决策或设计重算。
1 |
|
边界与自检
m=1时答案等于最大的k个元素之和;mk=n时所有位置必须选中;k=1时等于最大定长窗口和。这些退化情形提供独立参考。全零时答案为0,但位置不足仍不可达。
[1,2]与[3,4]能同时选吗?
可以。闭区间不共享位置,相邻不等于重叠。
收益非负,是否意味着状态可以全初始化为0?
某些变形可能借助非负性得到相同最终值,但已不能保持本文“恰好t段”的状态解释。不可达哨兵让证明与调试一致,不能把位置不足称为合法零收益方案。
来源与衔接
- Codeforces官方题页:题目契约、范围、样例与标签;证明、图与反例为原创。
- 474D计数DP:继续比较最优值与方案数两种不同的合并方式。