2014-03-08 10:25:45Morris
[其他題目][博弈] ?? Game
Description
還記得 UVa 11863 - Prime Game ? 這個問題也是差不多的。給一排數字，每次從輪流從最左側或右側挑出連續一段，其得分為最鄰近中心的元素。
求先手最多能贏多少分。// 先手一開始拿完所有元素必然勝利。
Input Format
輸入的第一行有一個正整數 T，代表測試資料的組數。
每一組測資的第一行有一個正整數 N (N < 2000)，代表數字的個數。
第二行有 N 個數字分別代表每個數字，每個數字 A[i] 為正整數 A[i] <
Output Format
對於每組測資輸出一行，輸出一個整數表示先手最多能贏多少。
Sample Input
2 5 3 3 3 3 3 8 3 1 5 2 10 1 1 5
Sample Output
3 7
題目解法：
擅長解博弈問題的人們啊，想必馬上想到最直觀的遞迴式。
dp[i][j] = max(A[k] - dp[i][k-1], A[k] - dp[k+1][j]) for i <= k <= j
但是這個算法卻要 O(n^3)
觀察遞迴式：
A[k] - dp[i][k-1] // 左起往右
A[k] - dp[k+1][j] // 右起往左
根據迭代順序，我們發現對於某一個元素的左起，往右抵達的會一直加長
對於 ML[i] = max(ML[i], A[k] - dp[i][k-1]) 即可
因此，把最裡面的 for 迴圈解決，降至 O(n^2)
#include <stdio.h>
#include <algorithm>
#include <stdlib.h>
using namespace std;
long long dp[2005][2005];
long long A[2005];
int main() {
int testcase, n;
int i, j;
scanf("%d", &testcase);
while(testcase--) {
scanf("%d", &n);
for(i = 0; i < n; i++)
scanf("%d", &A[i]);
long long ML[2005], MR[2005];
for(i = 0; i < n; i++)
ML[i] = MR[i] = -(1e+15);
int l, r;
for(i = 0; i < n; i++) {
for(j = 0; j + i < n; j++) {
l = j, r = j + i;
dp[l][r] = max(A[l], A[r]);
dp[l][r] = max(max(ML[r], MR[l]), dp[l][r]);
if(l -1 >= 0)
ML[r] = max(ML[r], A[l-1] - dp[l][r]);
if(r + 1 < n)
MR[l] = max(MR[l], A[r+1] - dp[l][r]);
}
}
printf("%lld\n", dp[0][n-1]);
}
return 0;
}