自动搬运

查看原文

来自洛谷，原作者为

	Zhao_daodao 赛场上要敢想，敢写

搬运于2025-08-24 22:49:01，当前版本为作者最后更新于2023-12-01 14:59:41，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

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$。