Easy Game

题目链接：

题意：

给出一个含n个数的序列（n≤100)，A和B每次能从这个序列的左端或右端取任意个数，这两个人很聪明，每次都会取对自己最优的情况（自己取得的数的和就是获得的分数，要使分数尽可能比对方的大），现在由A先开始取，求A的分数-B的分数的最大值。

 

题解：

有点博弈的感觉在里边，设dp[i,j]为区间[i,j]的最大值，则可以在[i,j]内取一个值k，使A先取k~j的所有值或者i~k的所有值，则dp[i][j]=max(dp[i][j],sum[j]-sum[k-1]-dp[i][k-1]),sum[j]-sum[k-1]-dp[i][k-1]))，假设A先取了k~j的所有值 则此时答案为sum[k~j]-剩余区间中B可以得到的最优情况，同理得A先取i~k时的答案

 

代码

#include<stdio.h>

#include<string.h>

#define Type int

#include<algorithm>

using namespace std;

const int N=101;

Type dp[N][N],sum[N],a[N];

Type mmax(Type x,Type y)

{

　　return x>y?x:y;

}

void clean()

{

　　for(int i=1;i<=100;++i)

　　for(int j=1;j<=100;++j)

　　dp[i][j]=(i>j?0:-999999999);

　　sum[0]=0;

}

void solve()

{

　　int n,T,w=0;

　　scanf("%d",&T);

　　while(T--)

　　{

　　　　scanf("%d",&n);

　　　　clean();

　　　　for(int i=1;i<=n;++i)

　　　　{

　　　　　　scanf("%d",&a[i]);

　　　　　　dp[i][i]=a[i];

　　　　　　sum[i]=sum[i-1]+a[i];

　　　　}

　　　　for(int len=1;len<=n;++len)

　　　　for(int i=1;i+len<=n;++i)

　　　　{

　　　　　　int j=i+len;

　　　　　　for(int k=i;k<=j;++k)

　　　　　　{

　　　　　　　　dp[i][j]=mmax(dp[i][j],sum[k]-sum[i-1]-dp[k+1][j]);

　　　　　　　　dp[i][j]=mmax(dp[i][j],sum[j]-sum[k-1]-dp[i][k-1]);

　　　　　　}

　　　　}

　　　　printf("Case %d: %d\n",++w,dp[1][n]);

　　}

}

int main()

{

　　solve();

　　return 0;

}