当前位置: 代码迷 >> 综合 >> CodeForces 731E Funny Game (博弈+DP)*好题
  详细解决方案

CodeForces 731E Funny Game (博弈+DP)*好题

热度:58   发布时间:2023-11-15 12:44:04.0

题目链接:http://codeforces.com/problemset/problem/731/E

题目描述:

给定一个整数序列,
按规则,每次玩家可以选择最左边的k个整数和作为自己的得分,
并把左边k个整数替换成一个整数,这个整数就是上次k个整数的和。

题目分析: 

这道题我感觉极富有技巧性。
首先我的想法比较朴素,前缀和性质这能看得出来,
dp[i][0]表示从i位置开始一号玩家先行动得到的最大差值,
dp[i][1]表示从i位置开始二号玩家行动得到的最大差值,
明显这样O(n*n)可以把答案求出来,但是时间不允许。
不难发现dp[n+1][0]=0,dp[n+1][1]=S[n],因为如果最后一步是一号玩家走到的,
明显差值要加上整体的和,我们要得到的答案是dp[0][0].

但是我们这里有个优化点,以二号玩家开始得到的差值,
和一号玩家得到的差值,其实就是符号问题,就是说一二号玩家在状态上是可以转换的,

所以设dp[i]表示先手拿前i个时候差值的最大值,因为对于每个人的开始来说,
因为不管两个人之前的差值如何,对于之后的选择策略是无影响的!
dp[i]=max{S[i]-dp[j]},j>i代码简化过后是如下的样子。

#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))
#define pii pair<int,int>
#define fi first
#define se second
#define mk(x,y) make_pair(x,y)
const ll mod=2e10+7;
const int maxn=2e5+10;
const int ub=1e6;
const double inf=1e-4;
ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}
/*
题目大意:给定一个整数序列,
按规则,每次玩家可以选择最左边的k个整数和作为自己的得分,
并把左边k个整数替换成一个整数,这个整数就是上次k个整数的和。题目分析:这道题我感觉极富有技巧性。
首先我的想法比较朴素,前缀和性质这能看得出来,
dp[i][0]表示从i位置开始一号玩家先行动得到的最大差值,
dp[i][1]表示从i位置开始二号玩家行动得到的最大差值,
明显这样O(n*n)可以把答案求出来,但是时间不允许。
不难发现dp[n+1][0]=0,dp[n+1][1]=S[n],因为如果最后一步是一号玩家走到的,
明显差值要加上整体的和,我们要得到的答案是dp[0][0].但是我们这里有个优化点,以二号玩家开始得到的差值,
和一号玩家得到的差值,其实就是符号问题,就是说一二号玩家在状态上是可以转换的,所以设dp[i]表示先手拿前i个时候差值的最大值,因为对于每个人的开始来说,
因为不管两个人之前的差值如何,对于之后的选择策略是无影响的!
dp[i]=max{S[i]-dp[j]},j>i代码简化过后是如下的样子。
*/
ll n,a[maxn];
ll dp[maxn][2];
int main(){a[0]=0;///cin>>n;rep(i,1,n+1) {cin>>a[i];a[i]+=a[i-1];}ll Max=a[n];for(int i=n-1;i>=2;i--){Max=max(Max,a[i]-Max);}cout<<Max<<endl;return 0;
}

 

  相关解决方案