uva 10891 Game of Sum(区间dp） - c++编程基础

题目大意：有n个数字排成一条直线，然后有两个小伙伴来玩游戏，每个小伙伴每次可以从两端（左或右）中的任意一端取走一个或若干个数（获得价值为取走数之和），但是他取走的方式一定要让他在游戏结束时价值尽量的高，最头疼的是两个小伙伴都很聪明，所以每一轮两人都将按照对自己最有利的方法去取数字，请你算一下在游戏结束时，先取数的人价值与后取数人价值只差（不要求绝对值）。

解题思路：这道题目想了一晚上，死憋着不看题解，结果写出的代码有点渣，dpx[i][j]表示在当前第i个数到第j个数中先取数的人可以达到的最高价值， dpy[i][j]为后取者最高可以达到的最高值。每次根据传入的参数flag判断是该谁去石子，通过引用返回最优解。

注意:数字可以为负数，所以标记的时候要注意，我是重新开了个数组vis.

#include   
#include   
const int N = 105;  
const int MAX = -0x3f3f3f3f;  
int n, num[N], sum[N], dpx[N][N], dpy[N][N], vis[N][N];  
  
void search(int a, int b, int& x, int& y, int flag) {  
    int &A = dpx[a][b], &B = dpy[a][b];  
    if (a + 1 == b)  
    A = num[b], B = 0;  
  
    if (!vis[a][b]) {  
    int s, f;  
    A = sum[b] - sum[a], B = 0;  
    for (int i = a + 1; i < b; i++) {  
        search(i, b, s, f, !flag);  
        if (flag && f + sum[i] - sum[a] > A)  
        A = f + sum[i] - sum[a], B = s;  
        else if (!flag && s + sum[i] - sum[a] > A)  
        A = s + sum[i] - sum[a], B = f;  
  
        search(a, i, s, f, !flag);  
        if (flag && f + sum[b] - sum[i] > A)  
        A = f + sum[b] - sum[i], B = s;  
        else if (!flag && s + sum[b] - sum[i] > A)  
        A = s + sum[b] - sum[i], B = f;  
    }  
    }  
    vis[a][b] = 1;  
  
    if (flag)  
    x = B, y = A;  
    else  
    x = A, y = B;  
}  
  
void solve() {  
    int s, f;  
  
    memset(dpx, MAX, sizeof(dpx));  
    memset(dpy, MAX, sizeof(dpy));  
    memset(vis, 0, sizeof(vis));  
  
    search(0, n, s, f, 0);  
    printf("%d\n", s - f);  
}  
  
int main() {  
    while (scanf("%d", &n) == 1 && n) {  
    // Read;  
    memset(num, 0, sizeof(num));  
    memset(sum, 0, sizeof(sum));  
    for (int i = 1; i <= n; i++) {  
        scanf("%d", &num[i]);  
        sum[i] = sum[i - 1] + num[i];  
    }  
  
    solve();  
    }  
    return 0;  
}