uva 12260 - Free Goodies(dp+贪心）

题目连接：uva 12260 - Free Goodies

题目大意：有n个糖果，每个糖果有p，j两个值，现在有两个人Petra和Jan，Prtra的取糖果方式是优先去p值大的j值小的；Jan取糖果的方式是尽量让自己开心值（取出糖果的j值和）大的情况下让Petra的开心值（取出糖果的p值和）也大，给出先选糖果的人，问说最后两人的开心值分别为多少。

解题思路：可以将糖果按照p值大小，再按j值小大的方式排序，排完的序列就是Petra的选取顺序，然后对于每个糖果，考虑Jan是否会选，dp[i][j]表示说前i个糖果中，Jan选取j个后的最大开心值，注意j ≤ (i+1)/2，因为如果轮到Petra选的话是不会将糖果让给Jan的。然后在Jan选取的过程中，要尽量保证说选走的p值要小，所以维护一个val[i][j]。

特别注意：Petra只关心眼前的利益，他只会取当前糖果中p值最大的，而Jan不一样，他不一定取最j值最大的，因为他知道j值大的不一定会被Petra先取走，所以他可以优先抢其他的。

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

using namespace std;
const int N = 1005;
struct state {
	int p, j;
}s[N];
int n, k, sum, dp[N][N], val[N][N];

bool cmp(const state& a, const state& b) {
	if (a.p != b.p) return a.p > b.p;
	return a.j < b.j;
}

void init () {
	char str[N];

	sum = 0;
	memset(dp, 0, sizeof(dp));
	memset(val, 0, sizeof(val));
	scanf("%d%s", &n, str);
	for (int i = 1; i <= n; i++) {
		scanf("%d%d", &s[i].p, &s[i].j);
		sum += s[i].p;
	}

	if (str[0] == 'P') k = 1;
	else k = 0;
	sort(s + 1, s + n + 1, cmp);
}

void solve () {
	for (int i = 1; i <= n-k; i++) {
		for (int j = 1; j <= (i+1)/2; j++) {
			if (dp[i-1][j] > dp[i-1][j-1] + s[i+k].j) {
				dp[i][j] = dp[i-1][j];
				val[i][j] = val[i-1][j];
			} else if (dp[i-1][j] == dp[i-1][j-1] + s[i+k].j) {
				dp[i][j] = dp[i-1][j];
				val[i][j] = min(val[i-1][j], val[i-1][j-1]+s[i+k].p);
			} else {
				dp[i][j] = dp[i-1][j-1] + s[i+k].j;
				val[i][j] = val[i-1][j-1] + s[i+k].p;
			}
		}
	}
	printf("%d %d\n", sum - val[n-k][(n-k+1)/2], dp[n-k][(n-k+1)/2]);
}

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