题目
【内存限制:$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$ 加上滑窗(即单调队列)优化
没时间码代码啊......