解題區/解題區 - 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;
}