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

01背包题目的雏形：

有N件物品和一个容量为V的背包。第i件物品的体积是c[i]，价值是w[i]。求解将哪些物品装入背包可使价值总和最大。

01背包的特点就是：每种物品仅有一件，可以选择放或不放。

其状态转移方程是：

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

方程之中，需要放置的是第i件物品，这件物品的体积是c[i],价值是w[i],

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

而f[i-1][v-c[i]]+w[i]则是代表将第i件放入背包之后的总价值，比较两者的价值，得出最大的价值存入现在的背包之中。

1.题解

此题是一个 01   背包输出序列问题，首先对乱序的数组排序，按起火的时间从小到大排序，

这是一种贪心策略，保证起火先的先抢救，然后进行 01 背包即可，

在求解中，需要标记一下某个状态下是否需要选择这个物品，最后用递归输出序列即可。

2.定义状态

dp_j  表示前 j 秒钟最多可以抢救的最大价值。

3.状态转移方程

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