首页 > itarticle > uva 12484 – cards

uva 12484 – cards

admin 11月 11, 2020 0

contents

Problem

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

Sample Input

Sample Output

1
2
3

10
7
57

Solution

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

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

#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("%lldn", dp[0][0]);
	}
	return 0;
}