解題區►解題區 - UVa

UVa 12260 - Free Goodies

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample
  4. 4. Solution

Problem

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

這裡可以明白有兩種策略

  • Petra 只求讓自己最高 - 貪心
  • Jan 自己最高的情況下，Petra 盡可能地高

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
3
4
Petra
100 80
70 80
50 80
30 50
4
Petra
10 1
1 10
6 6
4 4
7
Jan
4 1
3 1
2 1
1 1
1 2
1 3
1 4

Sample

1
2
3
170 130
14 16
9 10

Solution

Petra 使用貪心，將糖果數值按照 P 降排序，來作為 dp 時候 Petra 轉移用的順序，只要確保 Petra 會根據這個順序從大挑到小。

並且確保前 i 個糖果時，Jan 不會拿超過 i/2 個糖果 (否則表示交替順序不符合規則)，Jan 可以選擇先讓 Petra 分配到大的 P，而自己先去取大的 J。

dp[i][j] 表示前 i 個糖果，Jan 分配到 j 個的最佳策略 (J, P)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
#include <stdio.h> 
#include <string.h>
#include <algorithm>
#include <functional>
using namespace std;
const char name[2][10] = {"Petra", "Jan"};
pair<int, int> D[1024];
pair<int, int> dp[1024][512];
bool cmp(pair<int, int> p, pair<int, int> q) {
	if(p.first != q.first)
		return p.first > q.first;
	return p.second < q.second;
}
int main() {	
//	freopen("in.txt", "r+t", stdin);
//	freopen("out2.txt", "w+t", stdout); 
	int testcase, n;
	char s[1024];
	scanf("%d", &testcase);
	while(testcase--) {
		scanf("%d %s", &n, s);
		
		for(int i = 1; i <= n; i++) {
			int p, j;
			scanf("%d %d", &p, &j);
			D[i] = make_pair(p, j);
		}
		sort(D+1, D+1+n, cmp);
		
		int base = 0;
		if(!strcmp(name[0], s)) {
			base = D[1].first;
			for(int i = 1; i < n; i++)
				D[i] = D[i+1];
			n--;
		}
		memset(dp, 0, sizeof(dp));
		for(int i = 1; i <= n; i++) {
			for(int j = 0; j <= (i+1)/2; j++) {
				dp[i][j] = make_pair(dp[i-1][j].first, dp[i-1][j].second + D[i].first);
				if(j)
					dp[i][j] = max(dp[i][j], 
						make_pair(dp[i-1][j-1].first + D[i].second, dp[i-1][j-1].second));
			}
		}
		printf("%d %d\n", dp[n][(n+1)/2].second + base, dp[n][(n+1)/2].first);
	}
	return 0;
}