admin 管理员组

文章数量: 887021

Fire

fire

原题：
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 2000int 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);}
}

本文标签： Fire

版权声明：本文标题：Fire 内容由网友自发贡献，该文观点仅代表作者本人， 转载请联系作者并注明出处：http://www.freenas.com.cn/jishu/1687012134h55235.html， 本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌抄袭侵权/违法违规的内容，一经查实，本站将立刻删除。