原题： CF864E Fire
略
首先， 我们来证明一个东西:我们救东西的顺序为按销毁时间从早到晚， 那一定有一种情况是最优解。 证明: 若存在一个最优解不满足该证明， 则若我们重新将这几个东西按照销毁顺序重新排列， 那么我们只需要证明这个重新排列的顺序是可以成立的就行了。 那么我们来看一下， 设原来的前 i i i项和记为 S i Si Si， 第 i i i项为 A i Ai Ai， 新的分别为 S ′ i S'i S′i和 A ′ i A'i A′i。明显可得 S n = S ′ n , A n ≤ A ′ n Sn = S'n, An \le A'n Sn=S′n,An≤A′n, 那么第n项肯定成立， 而原序列去掉新序列中的第n项一定成立(这很显然嘛)，那么若长度为 n − 1 n - 1 n−1的序列变化成立， 那长度为 n n n的序列也成立。 而最后只有一项时是明显成立，所以证毕。 接下来我们回到原来的题目。首先我们定义状态为 d p [ i ] [ j ] dp[i][j] dp[i][j]， 表示前 i i i个元素在第 j j j时刻前救出的最大价值， 而第 i i i个元素的销毁时间我们知道， 所以我们就只能将这个元素放在销毁时间之前救出， 然后就如同 0 / 1 0/1 0/1背包一样救援时间当成体积， 价值当成价值。最后有一点要注意， 因为有销毁时间的存在， 所以我们的答案是在数组里最大的那个。
代码：
#include <cstdio> #include <algorithm> using namespace std; #define MAXN 2000 int st[MAXN + 5], sd[MAXN + 5], sp[MAXN + 5]; pair <int, int> s[MAXN + 5]; int dp[MAXN + 5]; int answer [MAXN + 5]; bool f[MAXN + 5][MAXN + 5]; int sa[MAXN + 5]; int main () { int n; int sum = 0; scanf ("%d", &n); for (int i = 1; i <= n; i ++) { scanf ("%d %d %d", &st[i], &sd[i], &sp[i]); s[i].first = sd[i]; s[i].second = i; sum = max (sum, sd[i]); } sort (s + 1, s + 1 + n); for (int i = 1; i <= n; i ++) { for (int j = s[i].first - 1; j >= st[s[i].second]; j --) { if (dp[j] < dp[j - st[s[i].second]] + sp[s[i].second]) { dp[j] = dp[j - st[s[i].second]] + sp[s[i].second]; f[i][j] = 1; answer[j] = answer[j - st[s[i].second]] + 1; } } } int smax = 0, maxl = 0; for (int i = 1; i <= sum; i ++) { if (dp[i] > smax) { smax = dp[i]; maxl = i; } } printf ("%d\n%d\n", smax, answer[maxl]); int tot = 0; for (int i = n, j = maxl; i > 0; i --) { if (f[i][j]) { sa[++tot] = i; j -= st[s[i].second]; } } for (int i = tot; i >= 1; i --) { printf ("%d ", s[sa[i]].second); } }