uva 10891 - Game of Sum(博弈，区间dp)-白红宇

uva 10891 - Game of Sum(博弈，区间dp)

阅读量：4072 次

发布时间：2019-05-25

本文共 1020 字，大约阅读时间需要 3 分钟。

题目大意：

有长度为n的正数序列，两个游戏者A 和B轮流取，A先取。每次玩家可以选择从序列左边或右边开始取一个或连续多个数字，问最终A最多可以比B大多少？

分析：

设f[l][r]表示对于区间[l,r]的序列，先取的人最多可以取的和。

那么，可以选择把[l,r]的所有数全部取光，或者只取一部分。

如果只取一部分,假设是[l,k]z这区间全部取，那么总共可以得到的和为sum[l,k]+(sum[k+1,r]-f[k+1][r])

所以状态转移为：

f[l][r] = sum[l][r]-min{ min{f[l][k], f[k+1][r]} }, l<=k<r

#include
   
    #include
    
     #include
     
      #include
      
       #include
       
        using namespace std;typedef long long int64;const int INF = 0x3f3f3f3f;int n, arr[110], sum[110];int f[110][110];int main(){    sum[0] = 0;    while(~scanf("%d", &n) && n){            for(int i=1; i<=n; ++i){            scanf("%d", &arr[i]);            sum[i] = sum[i-1] + arr[i];        }        memset(f, 0, sizeof(f));                for(int i=1; i<=n; ++i)            f[i][i] = arr[i];        for(int len=2; len<=n; ++len){            for(int l=1; l+len-1<=n; ++l){                int r = l+len-1;                                int tot = sum[r] - sum[l-1];                f[l][r] = tot;  // 把[l, r]全部取                for(int k=l; k