Fire

fire

原題：
CF864E Fire

題目

略

題解

思路

首先， 我們來證明一個東西:我們救東西的順序為按銷燬時間從早到晚， 那一定有一種情況是最優解。
證明:
若存在一個最優解不滿足該證明， 則若我們重新將這幾個東西按照銷燬順序重新排列， 那麼我們只需要證明這個重新排列的順序是可以成立的就行了。
那麼我們來看一下， 設原來的前$i$項和記為$Si$， 第$i$項為$Ai$， 新的分別為$S^{\prime }i$和$A^{\prime }i$。明顯可得$Sn=S^{\prime }n,An\le A^{\prime }n$, 那麼第n項肯定成立， 而原序列去掉新序列中的第n項一定成立(這很顯然嘛)，那麼若長度為$n-1$的序列變化成立， 那長度為$n$的序列也成立。 而最後只有一項時是明顯成立，所以證畢。
接下來我們回到原來的題目。首先我們定義狀態為$dp[i][j]$， 表示前$i$個元素在第$j$時刻前救出的最大價值， 而第$i$個元素的銷燬時間我們知道， 所以我們就只能將這個元素放在銷燬時間之前救出， 然後就如同$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);
	}
}