首页 > 其他 > 详细

BZOJ1783: [Usaco2010 Jan]Taking Turns

时间:2017-08-30 14:42:57      阅读:188      评论:0      收藏:0      [点我收藏+]

n<=700000个数,两人轮流取数,位置必须单增,输出两人都按最优策略得到的最大答案。

一开始看不懂“最优策略”,后来发现没有必要知道,f[i][1/0]--先/后手取数i最优答案,f[i][1]=a[i]+f[maxi][0],f[i][0]=f[maxi][1],maxi>i,因为先手取完后手必定转移到后面最优的先手策略。

然后WA了一发。这两人还是挺友好的不会陷害对方,就是说,有多个f[maxi][1]时,去下标最小的一个,让游戏进行地更持久!

技术分享
 1 #include<stdio.h>
 2 #include<string.h>
 3 #include<algorithm>
 4 #include<math.h>
 5 //#include<iostream>
 6 using namespace std;
 7 
 8 int n;
 9 #define maxn 700011
10 #define LL long long
11 LL a[maxn],f[maxn][2];
12 int main()
13 {
14     scanf("%d",&n);
15     for (int i=1;i<=n;i++) scanf("%lld",&a[i]);
16     f[n][1]=a[n];f[n][0]=0;int maxi=n;
17     for (int i=n-1;i>=1;i--)
18     {
19         f[i][1]=a[i]+f[maxi][0];
20         f[i][0]=f[maxi][1];
21         if (f[i][1]>=f[maxi][1]) maxi=i;
22     }
23     printf("%lld %lld\n",f[maxi][1],f[maxi][0]);
24     return 0;
25 }
View Code

 

BZOJ1783: [Usaco2010 Jan]Taking Turns

原文:http://www.cnblogs.com/Blue233333/p/7452991.html

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