首页 > 其他 > 详细

CF859C Pie Rules

时间:2019-09-15 18:51:00      阅读:183      评论:0      收藏:0      [点我收藏+]

洛咕

题意:有一个长度为\(n(n<=50)\)的序列,Alice和Bob在玩游戏.Bob先手掌握决策权.他们从左向右扫整个序列,在任意时刻,拥有决策权的人有如下两个选择:将当前的数加到自己的得分中,并将决策权给对方,对方将获得下一个数的决策权.将当前的数加到对方的得分中,并将决策权保留给自己,自己将获得下一个数的决策权.假定他们都使用最优策略,求他们最后分别能获得多少分.

分析:不能直接贪心或者DP,因为当前的操作是有后效性的.所以我们倒着DP,设\(f[i]\)表示从i到最后进行最优操作能够获得的最大分数(假设我们对第i+1次具有决策权,对第i次无决策权),所以\(f[i]=max(f[i+1],sum[i]-f[i+1])\).

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#include<queue>
#include<map>
#include<set>
#define ll long long
using namespace std;
inline int read(){
    int x=0,o=1;char ch=getchar();
    while(ch!='-'&&(ch<'0'||ch>'9'))ch=getchar();
    if(ch=='-')o=-1,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*o;
}
const int N=105;
int a[N],sum[N],f[N];
int main(){
    int n=read();
    for(int i=1;i<=n;++i)a[i]=read();
    for(int i=n;i>=1;--i)sum[i]=sum[i+1]+a[i];
    for(int i=n;i>=1;--i){
        f[i]=max(f[i+1],sum[i]-f[i+1]);
    }
    printf("%d %d\n",sum[1]-f[1],f[1]);
    return 0;
}

CF859C Pie Rules

原文:https://www.cnblogs.com/PPXppx/p/11523526.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!