Uva 10891 Game of Sum （经典博弈区间DP）

太过爱你忘了你带给我的痛 2021-12-14 02:37 217阅读 0赞

## 题意：给定一个长度为n的整数序列，A和B轮流取数，A先取，一次只能从左端或者右端取任意数量个数，所有数取完后求A的得分减去B的得分，A,B都采取最优策略。 ##

## 分析：这题用记忆化搜索很容易理解，总和是一定的，所以一个得分越高，另一个人的得分越低。当前状态总是最开始的状态的一个子状态。d(i,j): 先手取 i ~ j 最优策略下，得分最大值。d(i,j) = sum(i,j) - min(d(i+1,j),d(i+2,j),...,d(j,j),  d(i,j-1),d(i,j-2),...,d(i,i),0)，0表示全部取完；答案就是 d(1,n) - ( sum(1,n) - d(1,n) )； sum(i,j) 可以在 O(1) 的时间内求出来。 S\[i\] 是 1~ i 的和，那么 sum(i,j) = S\[j\] - S\[i-1\]。递推的做法可参考紫书P69。 ##

# #

## 记忆化搜索代码： ##

#include<bits/stdc++.h>
    using namespace std;
    
    int S[110], A[110], d[110][110], vis[110][110], n;
    
    int dp(int i, int j) {
      if(vis[i][j]) return d[i][j];
      vis[i][j] = 1;
      int m = 0; // 全部取光
      for(int k = i+1; k <= j; k++) m = min(m, dp(k,j));
      for(int k = i; k < j; k++) m = min(m, dp(i,k));
      d[i][j] = S[j]-S[i-1] - m; // 如果i从0开始编号，这里得判断一下是否i==0
      return d[i][j];
    }
    
    int main() {
      while(scanf("%d", &n) && n) {
        S[0] = 0;
        for(int i = 1; i <= n; i++) { scanf("%d", &A[i]); S[i]=S[i-1]+A[i]; }
        memset(vis, 0, sizeof(vis)); // 千万不要漏掉
        printf("%d\n", 2*dp(1,n)-S[n]);
      }
      return 0;
    }

## 递推代码： ##

#include<bits/stdc++.h>
    using namespace std;
    
    int S[110], A[110], d[110][110], vis[110][110], f[110][110], g[110][110], n;
    
    // f[i+1][j] = min{d(i+1,j),d(i+2,j)...,d(j,j)}
    // g[i][j-1] = min{d(i,j-1),d(i,j-2)...,d(i,i)}
    int main() {
      while(scanf("%d", &n) && n) {
        S[0] = 0;
        for(int i = 1; i <= n; i++) { scanf("%d", &A[i]); S[i]=S[i-1]+A[i]; }
        for(int i = 1; i <= n; i++) f[i][i] = g[i][i] = d[i][i] = A[i]; // 边界
        for(int L = 1; L < n; L++) // 按照L=j-i递增的顺序计算
          for(int i = 1; i+L <= n; i++) {
            int j = i+L;
            int m = 0; // m = min{f(i+1,j), g(i,j-1), 0}
            m = min(m, f[i+1][j]);
            m = min(m, g[i][j-1]);
            d[i][j] = S[j]-S[i-1] - m;
            f[i][j] = min(d[i][j], f[i+1][j]); // 递推f和g
            g[i][j] = min(d[i][j], g[i][j-1]);
          }
        printf("%d\n", 2*d[1][n]-S[n]);
      }
      return 0;
    }