[其他目][博弈] ?? Game＠Morris' Blog｜PChome Online 人新台

Morris' Blog 我在摸索我存在的意、生命的意、涵及值。有真正神手般的害，套用模式是大部分的情。那害的我存在的意何，托出神的存在？有候不能怪人不我，我已始省思，什我有人的原因，而是全要靠人。有候我我不同，那是因我做不到很多人能到的事情。我不到、玩不起、得不明、理解得不多，我缺少的文能力，就是一切一切能的判定。此，我不得能做些人有助的事情。我知道我自己是不服的性格，但在我不得不。我有能力，因此我必。我到底世界作什？充不定性，而我是法出拔萃，想一般人似乎也回不了了。越大的挑需要越力的支持，而我的支持是什？最近人，但都是失的局，人能接受，不需要言，不需要通，一切所想都表不出。
49的鼓 6站台

2014-03-08 10:25:45| 人2,101| 回0 | 上一篇 | 下一篇

[其他目][博弈] ?? Game

推 0 收藏 0 0 站台

Description

得 UVa 11863 - Prime Game ? 也是差不多的。

一排字，每次流最左或右挑出一段，其得分最近中心的元素。

求先手最多能多少分。// 先手一始拿完所有元素必然利。

Input Format

入的第一行有一正整 T，代表料的。

每一的第一行有一正整 N (N < 2000)，代表字的。

第二行有 N 字分代表每字，每字 A[i] 正整 A[i] < 109。

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;
}