uva 672 - Gangsters(dp)

題目連結：uva 672 - Gangsters

題目大意：給出n，K，T，表示一個酒店将要有n位客人到來，然後給出每個客人的ti，表示在ti時刻第i位客人來到酒店，ti ≤ T；再給出pi，表示第i位客人進入酒店為酒店帶來的收益；接着是si，表示第i位客人要進入酒店需要将門開到正好si的大小。酒店的門每時刻可以增加1，減少1或不動，問說酒店的收益最大值。

解題思路：dp[i]表示第i位客人在si的時刻進入酒店的最大收益，現将所有客人按照達到酒店的順序排序，然後對于每個客人i，考慮dp[j]（j<i)最大值，注意這裡是第i位客人進入酒店的最大收益，不一定dp[n]就是最優解，是以過程要維護最優解ans。還有注意也許第j為客人進入後，剩餘的時間無法讓門變成滿足i位客人進入的條件時不能考慮，以及第j位客人根本不能進入的情況。

#include <stdio.h>
#include <string.h>
#include <algorithm>

using namespace std;
const int N = 105;
struct state {
	int t, p, s;
}g[N];
int n, K, T, dp[N];

bool cmp(const state& a, const state& b) {
	return a.t < b.t;
}

void init () {
	scanf("%d%d%d", &n, &K, &T);
	for (int i = 1; i <= n; i++) scanf("%d", &g[i].t);
	for (int i = 1; i <= n; i++) scanf("%d", &g[i].p);
	for (int i = 1; i <= n; i++) scanf("%d", &g[i].s);
	sort(g + 1, g + n + 1, cmp);

	g[0].t = 0; g[0].s = 0;
	memset(dp, -1, sizeof(dp));
}

int solve() {

	dp[0] = 0;
	int ans = 0;
	for (int i = 1; i <= n; i++) {
		for (int j = 0; j < i; j++) {
			if (dp[j] == -1) continue;

			int u = g[i].t - g[j].t;
			int l = max(0, g[j].s - u), r = min(K, g[j].s + u);
			if (g[i].s >= l && g[i].s <= r) {
				dp[i] = max(dp[i], dp[j] + g[i].p);
			}
		}
		ans = max(dp[i], ans);
	}
	return ans;
}

int main () {
	int cas;
	scanf("%d", &cas);
	while (cas--) {
		init();
		printf("%d\n", solve());
		if (cas) printf("\n");
	}
	return 0;
}