动态规划TG.lv(1) （洛谷提高历练地）

动态规划TG.lv(1)

分析：每行不超过80个数字，直接区间DP即可，\(dp[i][j]\)表示区间\([i,j]\)之间取数可以得到的答案，每次向右或者向左扩展即可。但是这题烦人的地方在于大数

分析：状态可以想到是\(dp[i][j][a][b][k]\) 但是会爆内存，考虑转移的时候每次改变的是相对大小，所以可以优化掉一维。另外就是数组不能开LL，会爆内存

这个题和紫书上面的一个树形DP很像

Luogu题解区有大佬用贪心求

状态要用五层来表示，原因就是每个点可以涉及到的范围有五层

细节就不赘述了，题解区很详细的，这里就只做总结回顾。

分析：\(dp[i][j][2]\) 表示解决了\([i,j]\)之间的路灯，最后在左侧或者在右侧时的最小花费。转移的时候暴力转移。

分析：将垃圾按照时间排序，每个垃圾两种选择 =》 01背包，\(f[i]\)表示达到高度 i 时，最久可以坚持到什么时刻。