708      阿裏雲  技術社區[雲棲]

uva 10891 - Game of Sum

題意：

   A,B兩人依次從數組兩邊拿數字，每次任選一邊拿走1+個，A先手，問最後A比B大多少

設代表i,j子序列先手可以取得的最大差值

轉移方程為

有個狀態，個轉移，總複雜度為結果為f(1,n)

也可設f(i,j)為子序列和，則結果為2f(1,n)-sum(n)

轉移方程為 f(i,j)=sum(i,j)-min{d(i+1,j)................}

利用i.j差值遞增做轉移可以將複雜度降為n^2

/*
author:jxy
lang:C/C++
university:China,Xidian University
**If you need to reprint,please indicate the source**
*/
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <algorithm>
using namespace std;
#define inf 1000000000
bool vis[101][101];
int ans[101][101];
int n;
int sum[101];
int calc(int i,int j)
{
    if(i>j)return 0;
    if(vis[i][j])return ans[i][j];
    vis[i][j]=1;
    int t;
    int &tans=ans[i][j];
    tans=-inf;
    for(t=i+1;t<=j+1;t++)
    {
        tans=max(tans,sum[t-1]-sum[i-1]-calc(t,j));
    }
    for(t=j-1;t>=i;t--)
    {
        tans=max(tans,sum[j]-sum[t]-calc(i,t));
    }
    return tans;
}
int main()
{
    while(~scanf("%d",&n)&&n)
    {
        int i;
        sum[0]=0;
        for(i=1;i<=n;i++)
        {
            scanf("%d",&sum[i]);
            sum[i]+=sum[i-1];
        }
        memset(vis,0,sizeof(vis));
        printf("%d\n",calc(1,n));
    }
}

最後更新：2017-04-03 12:54:51

  上一篇： python 2.7 自定義 RPM 編譯[備忘]

  下一篇： HDU1232暢通工程