首页 > 代码库 > BZOJ 2017: [Usaco2009 Nov]硬币游戏(A Coin Game)

BZOJ 2017: [Usaco2009 Nov]硬币游戏(A Coin Game)

题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=2017

参考题解:http://www.mamicode.com/info-detail-1582288.html

解:看的时候觉得是动归,然而不会设也不会列,看了半天别人的题解。。。

首先我们用f[i][j]来表示还剩下后i个硬币要取,上一步取了j个硬币,接下来的步骤中能获得的最大价值。

然后呢,假设在这一步是第一个人取,要取k个,k<=min(2*j,i),很显然,因为第二个人也会取最优,他剩下能得到的最大值就是f[i-k][k],所以f[i][j]=sum[i~n]-min(f[i-k][k])。

当然这么枚举k是会超时的,我们又可以发现f[i][j]与f[i][j-1]的更新中只多了两次,即能用来更新f[i][j-1]的k,一定能用来更新f[i][j],除此之外还有k=2*j-1和k=2*j可以更新f[i][j]。所以我们在开始的时候只要让f[i][j]=f[i-1][j],然后枚举多出的两个k,就能完成更新了,复杂度O(n^2);

为了方便,我们直接倒过来输入。

程序:

#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
using namespace std;
int n,a[2010],sum[2010],x,f[2010][2010];
int main()
{
  scanf("%d",&n);
  for (int i=n;i>=1;i--) scanf("%d",&a[i]);
  for (int i=1;i<=n;i++) sum[i]+=sum[i-1]+a[i];
  for (int i=1;i<=n;i++)
   for (int j=1;j<=n;j++)
    {
         f[i][j]=f[i][j-1];
       int k=2*j-1;
       if (k<=i) f[i][j]=max(sum[i]-f[i-k][k],f[i][j]);
     k+=1;
       if (k<=i) f[i][j]=max(sum[i]-f[i-k][k],f[i][j]);
    }
  printf("%d\n",f[n][1]);
  return 0;
}

 

BZOJ 2017: [Usaco2009 Nov]硬币游戏(A Coin Game)