https://codeforces.com/problemset/problem/864/E

01背包題目的雛形：

有N件物品和一個(gè)容量為V的背包。第i件物品的體積是c[i]，價(jià)值是w[i]。求解將哪些物品裝入背包可使價(jià)值總和最大。

01背包的特點(diǎn)就是：每種物品僅有一件，可以選擇放或不放。

其狀態(tài)轉(zhuǎn)移方程是：

f[i][v]=max{f[i-1][v],f[i-1][v-c[i]]+w[i]}

方程之中，需要放置的是第i件物品，這件物品的體積是c[i],價(jià)值是w[i],

因此f[i-1][v]代表的就是不將這件物品放入背包，

而f[i-1][v-c[i]]+w[i]則是代表將第i件放入背包之后的總價(jià)值，比較兩者的價(jià)值，得出最大的價(jià)值存入現(xiàn)在的背包之中。

1.題解

此題是一個(gè) 01? ?背包輸出序列問(wèn)題，首先對(duì)亂序的數(shù)組排序，按起火的時(shí)間從小到大排序，

這是一種貪心策略，保證起火先的先搶救，然后進(jìn)行 01 背包即可，

在求解中，需要標(biāo)記一下某個(gè)狀態(tài)下是否需要選擇這個(gè)物品，最后用遞歸輸出序列即可。

2.定義狀態(tài)

dp_j? 表示前 j 秒鐘最多可以搶救的最大價(jià)值。

3.狀態(tài)轉(zhuǎn)移方程

dp_j ← max ?{dp_j,dp_{j-t_i}+p_i}