首页 > 代码库 > UVA10891 Game of Sum 区间DP
UVA10891 Game of Sum 区间DP
好像带点博弈，又好像没有。
设dp[i][j] 为[i,j]区间内先手得分的最大值(这里的先手不一定是指player A!)
这时候只需要枚举出现在的先手会取哪一边，取几个，然后现在的最优状态就可以由以前的状态推出来
那么dp[i][j] = sum[i,j]-min(dp[i+1][j],dp[i+2][j],....,dp[j][j],dp[i][j-1],...,dp[i][i],0);
举个例子：
例如说sum[i,j]-dp[i+1][j]是指先手取了[i,j]的第一个元素即 A[i]，此后该另外一人取，dp[i+1][j]就是另外一人能取得的最大值。
最后的要的结果是先手减另外一人的结果
即dp[1][n]-(sum[1,n]-dp[1][n]) = 2*dp[1][n]-sum[i,j]
#include <cstdio>#include <algorithm>using namespace std;const int maxn = 105;int dp[maxn][maxn],sum[maxn];int main(){ int n; while(~scanf("%d",&n) && n) { dp[0][0] = 0; sum[0] = 0; for(int i = 1;i<=n;++i) { scanf("%d",&dp[i][i]); sum[i] = sum[i-1]+dp[i][i]; } for(int r = 2;r<=n;++r) for(int i = 1;i<=n-r+1;++i) { int j = i+r-1, t = 0; for(int k = i+1;k<=j;++k)t = min(t,dp[k][j]); for(int k = i;k<j;++k)t = min(t,dp[i][k]); dp[i][j] = sum[j]-sum[i-1]-t; } printf("%d\n",2*dp[1][n]-sum[n]); } return 0;}
UVA10891 Game of Sum 区间DP
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。