DP 杂题选做

标签：min sum times 这题 杂题 DP dis

概率期望 DP 学习笔记
树形 DP 学习笔记

其余就不具体分类了。

P1220 关路灯

题解说这是区间 DP 经典题，但我以前居然没听说过，这下尴尬了。
设 \(f_{i,j,0/1}\) 表示关掉区间 \([i,j]\) 所有灯，人在点 \(i/j\) 消耗的最少功率。
那么

\[f_{i,j,0}=\min(f_{i+1,j,0}+dis_{i,i+1}\times (sum-s_{i+1,j}),f_{i+1,j,1}+dis_{i,j}\times (sum-s_{i+1,j})) \]

\[f_{i,j,1}=\min(f_{i,j-1,1}+dis_{j-1,j}\times (sum-s_{i,j-1}),f_{i,j-1,0}+dis_{i,j}\times (sum-s_{i,j-1})) \]

P2466 [SDOI2008] Sue 的小球

做完上面那题这题就很好办了。
这题满足关系式 \(y=s_0-vt\)，把功率换成速度，那这题就是求最小的价值乘移动距离的值。
于是就做完了（？

标签：min,sum,times,这题,杂题,DP,dis
From： https://www.cnblogs.com/ying-xue/p/16982444.html