解題區/解題區 - UVa

UVa 11932 - Net Profit

contents

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

Problem

兩個人在玩一場工廠收購遊戲，工廠之間呈現一張連通圖。先手可以隨機挑一個工廠開始，之後兩個人輪流收購在附近的工廠 (只能選擇盤面上已經收購工廠附近相鄰的工廠)，收購工廠帶來的利益有正、有負。

請問兩邊都是完美玩家，則最多可以贏對方多少分。

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
2
25 -20
1
1 2
3
15 15 -5
2
1 2
2 3
2
30 30
1
1 2
0

Sample Output

1
2
3
First player wins! 25 to -20.
Second player wins! 15 to 10.
Tie game! 30 all.

Solution

工廠數量最多 16 個，可以狀態壓縮 dp[2^16]，最大化分差下去完成。

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
#include <stdio.h> 
#include <string.h>
#include <vector>
#include <algorithm>
using namespace std;
int profit[16], dp[1<<16];
int g[16], used[1<<16];
int dfs(int s, int n) {
    if (used[s])	return dp[s];
    if (s == 0)		return 0;
    used[s] = 1;
    int &ret = dp[s];
    int vs = (1<<n)-1 - s;
    ret = -0x3f3f3f3f;
    for (int i = 0; i < n; i++) {
        if (s == (1<<n)-1 || ((g[i]&vs) && ((s>>i)&1))) {
            ret = max(ret, profit[i] - dfs(s^(1<<i), n));
        }
    }
    return ret;
}
int main() {
    int n, m, x, y;
    while (scanf("%d", &n) == 1 && n) {
        int sum = 0;
        for (int i = 0; i < n; i++) {
            scanf("%d", &profit[i]);
            g[i] = 0, sum += profit[i];
        }
        scanf("%d", &m);
        for (int i = 0; i < m; i++) {
            scanf("%d %d", &x, &y);
            x--, y--;
            g[x] |= 1<<y, g[y] |= 1<<x;
        }
        
        memset(used, 0, sizeof(used));
        int mxDiff = dfs((1<<n)-1, n);
        if (mxDiff == 0) {
            printf("Tie game! %d all.\n", sum/2);
        } else if (mxDiff > 0) {
            printf("First player wins! %d to %d.\n", (sum + mxDiff)/2, (sum - mxDiff)/2);
        } else {
            printf("Second player wins! %d to %d.\n", (sum - mxDiff)/2, (sum + mxDiff)/2);
        }
    }
    return 0;
}