Uva(10891)(Game of Sum)

链接：https://vjudge.net/problem/UVA-10891
思路：其实我一开始没有看出来这是一个动态规划的题目，不过我们可以来思考一下，设d(i,j)为先手所能取得的最好的最大的分差，那么我们怎么表示这个d(i,j)呢，我们知道，总和是一定的，你取了多少分，马上可以算出对手取了多少分，那么d(i,j)就可以i表示为sum(i,j)-min(d(i+1,j),d(i+2,j).......d(i,j-1),d(i,j-2).....d(i,i+1),0)(注意0表示对手决策用完，即我一把把所有的都全部抓完，对手从而没有东西可以抓了，这种情况一定不要漏掉！！！)，然后用dd[][]保存已经计算出的值，记忆式搜索求出答案。
代码：

#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
using namespace std;
int n,sum[101][101],a[101],dd[101][101];

int d(int i,int j){
    if(dd[i][j]!=0)return dd[i][j];//保存已经搜索出的值
    if(i==j)return a[i];
    int minn = 0;//一把抓完所有的
//取最小值
    for(int k=i+1;k<=j;k++){
        minn = min(minn,d(k,j));
    }
    for(int k=j-1;k>=i;k--){
        minn = min(minn,d(i,k));
    }
    dd[i][j] = sum[i][j] - minn;//保存当前最优解
    return dd[i][j];//返回最优解
}

int main(){
//  freopen("in.txt","r",stdin);
//  freopen("out.txt","w",stdout);
    while(cin>>n&&n){
        memset(sum,0,sizeof(sum));
        memset(dd,0,sizeof(dd));
        for(int i=1;i<=n;i++)cin>>a[i];
            for(int i=1;i<=n;i++){
                for(int j=i;j<=n;j++){
                    for(int k=i;k<=j;k++){
                        sum[i][j]+=a[k];
                    }
                }
            }
    cout<<2*d(1,n)-sum[1][n]<<endl;//结果等于d(i,j)-(sum(i,j)-d(i,j))，即原式
    }
    return 0;
}

老刘的o（n^2）解法暂时没看懂,先放这里吧

Uva(10891)(Game of Sum)