最基础的东西不用解释，一定是 $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$ 加上滑窗（即单调队列）优化
没时间码代码啊......
原文：https://www.cnblogs.com/MachineryCountry/p/11728842.html