解題區/解題區 - UVa

UVa 12484 - Cards

contents

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

Problem

每一個序列，每次只能拿走首元素或者尾元素，Alberto 和 Wanderley 輪流取牌，由 Alberto 先手，請問遊戲最後 Alberto 最高能得多少分，而 Wanderley 會盡力阻止她。

Sample Input

1
2
3
4
5
6
4
0 -3 5 10
4
0 -3 5 7
4
47 50 -3 7

Sample Output

1
2
3
10
7
57

Solution

照著 dp 的思路下去，因為要輪流取，而 Wanderley 只會想要最小化 Alberto 分數，不會考慮自己的分數，因此轉移的時候會盡可能地小。

dp[i][j] 表示當前剩餘長度為 i, 起始首元素為 j，由於狀態太多，必須靠滾動數組來完成 dp。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include <stdio.h> 
#include <string.h>
#include <algorithm>
using namespace std;
int main() {
    int n, a[10005];
    long long dp[2][10005];
    while(scanf("%d", &n) == 1) {
        for(int i = 0; i < n; i++)
            scanf("%d", &a[i]);
        memset(dp, 0, sizeof(dp));
        for(int i = 0; i < n; i++) {
            for(int j = 0; j + i < n; j++) {
                if((i&1) == 1)
                    dp[0][j] = max(dp[1][j+1] + a[j], dp[1][j] + a[j+i]);
                else
                    dp[1][j] = min(dp[0][j+1], dp[0][j]);
            }
        }
        printf("%lld\n", dp[0][0]);
    }
    return 0;
}