【Tyvj1075】硬币游戏

2014-05-16
竞赛题解 / 动态规划
TYVJ

描述 Description

最初地面上有一堆 n 个硬币 (5<=n<=2000)，从上面数第 i 个硬币的价值为 C_i(1<=C_i<=100000);

游戏开始后，A 先取一枚或两枚硬币。如果 A 取了一枚，那么 B 可以继续取一枚或两枚；如果 A 取了两枚，那么 B 可以取一到四枚硬币。每次都只能从最上面取。每一次，当前取硬币的人都至少取一枚硬币，最多可以取他的对手上一次取硬币数目的两倍。当没有硬币可取的时候，游戏就结束了。

然后，他们就可以用得到的硬币向 John 买东西，当然，他们游戏的目的就是要尽可能使自己得到的硬币价值更大。现在你的任务是，求出在两个人都想得到更大价值的情况下，游戏结束后，第一个人最多能得到的硬币价值。

输入格式 InputFormat

第 1 行： 一个整数，N（5<=N<=2000）。
第 2 到 n+1 行： 第 i+1 行代表从上数第 i 枚硬币的价值。

输出格式 OutputFormat

一行：一个数字，第一个人能得到的最大价值。

样例输入 SampleInput

9
634
356
245
998
757
170
95
299
337

样例输出 SampleOutput

2214

来源 Source

USACO Nov09 Ag

Tyvj 1075

代码 Code

DP.f[i,j] 表示剩下的 x 枚硬币中第一人取 2*j 个的最大值。sum 数组预处理。注意数组边界问题 DEV-C++ 中数组下标小于零是不会报错的 = = 但是测评网站上会 RE=_=#

#include <stdio.h>
#include <iostream>
#include <cstring>
#include <algorithm>
#include <cmath>
using namespace std;
int a[5000],sum[5000];
int f[2001][2001];
int i,j,t,n,m,l,r,k,z,y,x;
int main()
{
    memset(f,0,sizeof(f));
    memset(sum,0,sizeof(sum));
    scanf("%d",&n);
    for (i=1;i<=n;i++) 
    {
        scanf("%d",&a[i]);
    }
    for (i=1;i<=n;i++) sum[i]=sum[i-1]+a[n-i+1];
    for (i=1;i<=n;i++) for (j=1;j<=n;j++)
    {
        f[i][j]=f[i][j-1];
        if (i-2*j+1>=0) f[i][j]=max(f[i][j],sum[i]-f[i-2*j+1][2*j-1]);
        if (i-2*j>=0) f[i][j]=max(f[i][j],sum[i]-f[i-2*j][2*j]);
    }
    printf("%d\n",f[n][1]);
    return 0;
}