首页 > 代码库 > [usaco][DP]游戏 A Game
[usaco][DP]游戏 A Game
题目梗概
n个数字，A和B每次执行一次动作，动作是可以从左边或者右边选择一个数字加入自己，求两个人都在执行最优策略的情况下，B玩家的获胜次数。
思考
显而易见的想法是每次从左端取和右端取数构成最大值，那我可不可以从这个条件入手dp每次是取左端的最大值和取右端的最大值，但是我水平有限。没想出来转移方程。
其次想法是我可以用区间dp的思想，每次维护一个区间的最大值，不断加入新的区间再计算。但是难点在于先后手问题。
在苦于无解的情况下看了下题解的方程，dp[i][j]表示先手在区间[i,j]的最大值。（后手就是总和减去先手的最大值）
sum[i][j]表示区间[i,j]前缀和
$dp[i][j]=max(sum[i][j]-dp[i+1][j],sum[i][j]-dp[i][j-1])$
$dp[i][j]=sum[i][j]-min(dp[i+1][j],dp[i][j-1])$
因为dp[i+1][j]和dp[i][j-1]在dp[i][j]之前就被计算过了，所以可以优化一下空间复杂度 O(n) 时间复杂度O($n^2$)
代码实现
#include <cstdio>#include <algorithm>int n,a[202],dp[202],sum[202];inline int get(){ char ch; int res = 0; bool f = true; while (((ch = getchar()) < ‘0‘ || ch > ‘9‘) && ch != ‘-‘); if (ch == ‘-‘) f = false; else res = ch - ‘0‘; while ((ch = getchar()) >= ‘0‘ && ch <= ‘9‘) res = (res << 3) + (res << 1) + ch - ‘0‘; return f? res : -res;}int main(){ n = get(); for(register int i=1;i<=n;++i){ a[i] = get(); sum[i]=sum[i-1]+a[i]; dp[i]=a[i]; } for(register int len=1;len<n;len++){ for(register int i=1;i+len<=n;i++){ dp[i]=sum[i+len]-sum[i-1]-std::min(dp[i],dp[i+1]); } } printf("%d %d",dp[1],sum[n]-dp[1]); return 0;}
[usaco][DP]游戏 A Game
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。