首页 > 代码库 > cf731E
cf731E
题意:一个游戏,由n张贴纸组成。贴纸排成一排,并且纸条上标有数字,玩家轮流揭下m张从左到右连续的纸条(m大等2),揭下后玩家得分累加这些纸条的sum,并且在剩下纸条最左边贴上新的纸条,数值为揭下纸条的sum。最后只剩一张纸条时游戏结束。每个玩家的策略是使敌我分差尽可能大。求这个分差。
这道题是那一场最难的题,交的人最少,然而代码只有几行(一个for循环搞定
题解引入了一个“zero-sum game”来阐述这一类游戏,并且说这一类游戏通常用dp解(%%%
我们发现每个状态只跟我们已经取走了多少张纸条有关,我们设状态dp[i]表示已经取走i个纸条,一开始分差为0的状态,装的值为这种状态下最大分差
状态转移为dp[i]=max(sum[j]-dp[j]) i<j<=n
推的时候维护最大值,O(n)草翻这题(%%%%
1 #include<bits/stdc++.h> 2 using namespace std; 3 #define N 200005 4 int n,s[N],dp[N],maxx; 5 int main(){ 6 scanf("%d",&n); for(int a,i=1;i<=n;i++) scanf("%d",&a),s[i]=s[i-1]+a; 7 maxx=s[n]; 8 for(int i=n-1;i>=1;i--) 9 dp[i]=maxx,maxx=max(maxx,s[i]-dp[i]); 10 printf("%d\n",dp[1]); 11 return 0; 12 }
cf731E
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。