P1075 - 硬币游戏
From
price
Normal (OI)
总时限：10s 内存限制：128MB 代码长度限制：64KB
背景 Background
农民John的牛喜欢玩硬币，所以John就为它们发明了一个新的两人硬币游戏，叫做Xoinc。
描述 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 [复制数据]
513172
样例输出 SampleOutput [复制数据]
9
这道题确实一看就知道时DP，但是我连蒙带猜一个小时才把样例调过。按照博弈问题的惯例，这个状态的最优值便是前驱状态中的最优的转移而来。
为什么不是前驱中最劣的呢？因为如果我们按照第一个思路，一个人如果希望通过自己行动使自己的价值最大，他必然会选择一个对方获益最少的前驱状态，然而当他选择后，对方完全可以通过之前的决策使这个前驱状态不被走到。反过来，如果我们选择了前驱状态最优的状态，就假定对方足够聪明，能尽可能避免损失，正好符合题意。
剩下就是DP优化了，优化部分很水，就不细讲了。
#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
#define MAXN 2100
#define INF 0x3f3f3f3f
int dp[MAXN][MAXN];
int g[MAXN][MAXN];
int c[MAXN],sum[MAXN];
int main()
{
freopen("input.txt",
"r",stdin);
//freopen("output.txt","w",stdout);
int i,j,k,n,m;
int x,y,z;
scanf("%d",&
n);
for (i=
1;i<=n;i++
)
{
scanf("%d",c+
i);
}
for (i=n;i>=
1;i--
)
sum[i]=sum[i+
1]+
c[i];
for (i=
0;i<MAXN;i++
)
for (j=
0;j<MAXN;j++
)
dp[i][j]=g[i][j]=-
INF;
for (i=
0;i<=n;i++
)
{
dp[n-i+
1][i]=sum[n-i+
1];
for (j=i;j<=n;j++
)
{
g[n-i+
1][j]=sum[n-i+
1];
}
}
for (i=n;i>=
1;i--
)
{
for (j=
1;i+j<=n;j++
)
{
if (g[i+j][min(j*
2,n)]==-INF)
continue;
dp[i][j]=sum[i]-g[i+j][min(j*
2,n-
i)];
g[i][j]=max(g[i][j-
1],dp[i][j]);
}
}
cout<<max(dp[
1][
1],dp[
1][
2])<<
endl;
}
转载于:https://www.cnblogs.com/mhy12345/p/4046320.html
相关资源：25个经典网站源代码
