题目

【内存限制:$256 MiB$】【时间限制:$1000 ms$】
标准输入输出 】【题目类型:传统】评测方式:文本比较】


题解

做题思路

最基础的东西不用解释,一定是 $dp$ 一类的题。

然后开始考虑 $dp$ 定义。

考场定义:$dp[i][j]$:在第 $i$ 号位以及之前,一共捡了 $j$ 个宝箱。

但是很显然,这个 $dp$ 定义漏洞百出,考场能得 $50pts$ 已经拜我今天大吉所赐了

正解

首先考虑朴素 $dp$ :

定义三维 $dp[i][j][k]$:推到第 $i$ 位,并且前一位取的是 $j$ ,一共已经捡了 $k$ 个宝箱。

不用说状转了,$O(N^2)$ 的 $dp$ ,而且空间......

考虑将其简单化处理,简化状态:

$dp[i]$:第 $i$ 位一定取,并且在前面方案一定合法时的最大利益

那么状转:$dp[i]=Max(dp[j])+a[i]*k^x,j\in [i-M+1,i)$

但是这个式子有个问题,前面选了多少个宝箱我们是不知道的,也可以说前面的状态其实是对后面的状态有影响的

即这个 $x$ 参数我们是不知道的,也就是说我们可能还需要一维来记录已经取了多少个宝箱了。

然后空间就炸了。

这里采用一个很巧妙的方法,我们倒着推状态,那么状转:

$$dp[i]=kMax\{dp[j]\}+a[i],j\in (i,i+M-1]$$

它巧妙在何处?

前面的分析:前面怎么取的是会对后面造成影响

那么我们反其道而行:后面的状态怎么取是不会对前面的状态造成影响的。

最后这就成了一个简单 $dp$ 加上滑窗(即单调队列)优化

没时间码代码啊......
01-07 06:16