P9506 题解

· · 题解

solution

感觉接近一道板子题。

首先考虑一条链的情况。

定义 dp_i 表示当前考虑到了第 i 个课程， 定义 cost_{i,j} 表示 \sum\limits_{k=i}^{j}b_k。

对于 dp_i 有两种可能：

  1. 买整一个课程，即 \max_{1\le j<i}{dp_j}+cost(i+1,i+k-1)。
  2. 买一部分课程，即 dp_{i-1}+b_{i+k-1}。

正确性：如果买一部分课程，那么最优解一定可以全部不买，否则已经被 dp_{i-1} 考虑到了。

此时有一个及其板的思路：钦定第一个买还是不买，因为 k\le n，所以之后的转移显然是正确的。

那么只用跑两种情况，即第一个课程选还是不选，就可以包含所有情况了。

只需要调整一下转移方程就行了。

最后的答案是 \max_{i=1}^{n}dp_i。