P3507 [POI2010]GRA-The Minima Game

题目描述

Alice and Bob learned the minima game, which they like very much, recently.

The rules of the game are as follows.

A certain number of cards lies on a table, each inscribed with a positive integer.

The players make alternate moves, Alice making the first one.

A move consists in picking an arbitrary positive number of cards from the table.

For such move the player receives a number of points equal to the minimum of the numbers inscribed on the cards he collected.

The game ends when the last card is removed from the table.

The goal of each player is maximizing the difference between their and their opponent's score.

Alice and Bob have duly noted that there is an optimal strategy in the game.

Thus they are asking you to write a program that, for a given set of cards, determines the outcome of the game when both players play optimally.

给出N个正整数,AB两个人轮流取数,A先取。每次可以取任意多个数,直到N个数都被取走。每次获得的得分为取的数中的最小值,A和B的策略都是尽可能使得自己的得分减去对手的得分更大。在这样的情况下,最终A的得分减去B的得分为多少。

输入输出格式

输入格式:

In the first line of the standard input there is one integer n(1<=n<=1000000) given, denoting the number of cards. The second line holds n positive integers k1,k2,...,kn(1<=ki<=10^9) separated by single spaces, that are inscribed on the cards.

输出格式:

Your program should print out a single line with a single integer to the standard output - the number of points by which Alice wins over Bob, assuming they both play optimally; if it is Bob who has more points, the result should be negative.

输入输出样例

输入样例#1:

3
1 3 1

输出样例#1:

2

如果选了i,那么>=i的数都要选。

否则对方一定会更优。

证明:

假如选完>=i的数的状态为s1,没选完的为s2。

对方可以先选完>=i的数,那么他接下来面对的状态就是s1了。

所有在s2下,一切s1有的决策他都能选择。

同时他还多了一些决策。

所有s2下他一定比s1优。

所以我们先将n个数从小到大排序。

f[i]表示剩下了1..i这个前缀的max(先手-后手)。

枚举先手决策,f[i]=max(a[j]-f[j-1]),j=1..i

边界是f[0]=0。

a[j]-f[j-1]的前缀max是很好维护的。

 1 #include<cstdio>
 2 #include<cstring>
 3 #include<cmath>
 4 #include<algorithm>
 5 using namespace std;
 6 const int MAXN=12700000;
 7 inline void read(int &n)
 8 {
 9     char c=getchar();n=0;bool flag=0;
10     while(c<'0'||c>'9')    c=='-'?flag=1,c=getchar():c=getchar();
11     while(c>='0'&&c<='9')    n=n*10+c-48,c=getchar();flag==1?n=-n:n=n;
12 }
13 int a[MAXN];
14 int n;
15 int main()
16 {
17     int n;read(n);
18     int MAX=-1,MIN=0x7fff;
19     for(int i=1;i<=n;i++)    read(a[i]);
20     sort(a+1,a+n+1);
21     int ans=0;
22     for(int i=1;i<=n;i++)
23         if(ans<a[i]-ans)    
24             ans=a[i]-ans;
25     printf("%d",ans);
26     return 0;
27 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏AI研习社

放弃深度学习?我承认是因为线性代数

深度学习:作为机器学习的一个子域,关注用于模仿大脑功能和结构的算法:人工神经网络。

12520
来自专栏深度学习计算机视觉

矩阵乘法的Strassen算法+动态规划算法(矩阵链相乘和硬币问题)

矩阵乘法的Strassen ---- 这个算法就是在矩阵乘法中采用分治法,能够有效的提高算法的效率。 先来看看咱们在高等代数中学的普通矩阵的乘法 ? 两个矩阵相...

1.1K60
来自专栏专知

【论文推荐】最新八篇情感分析相关论文—注意力网络、多模态情感分析、情感分析局限性、跨语言情感分类、多语言情感分析

【导读】专知内容组今天推出最新八篇情感分析(Sentiment Analysis)相关论文,欢迎查看!

80120

如何实现自然语言处理的集束搜索解码器

自然语言处理任务(例如字幕生成和机器翻译)涉及生成单词序列。

43180
来自专栏数值分析与有限元编程

有限元类型

从变分原理角度来看,按照所选取的独立自变函数的类型,可以分为如下几种类型: 1 协调类型 以位移作为独立自变函数,使用的变分原理是最小势能原理。作为独立自变函...

29240
来自专栏ACM算法日常

UVA297:黑白图像 Quadtrees(四分树)

四象树是每个内结点均有4个子结点的特殊四叉树,它可用于描述平面上黑白图像。平面上的黑白图像是32行×32列的正方形,每个格子称为1个象素,是最小的图像单位。正方...

17530
来自专栏深度学习计算机视觉

数据挖掘之认识数据学习笔记相关术语熟悉

相关术语熟悉 首先认识数据的属性 属性是一个数据字段,表示数据对象的一个特征 标称属性 标称属性的值是一些符号或事物的名称,这一些值可以看做是枚举的 比如,职...

28360
来自专栏大数据挖掘DT机器学习

非监督学习算法:异常检测

什么是异常(outlier)?Hawkins(1980)给出了异常的本质性的定义:异常是在数据集中与众不同的数据,使人怀疑这些数据并非随机偏差,而是产生于完全不...

73450
来自专栏ml

调参过程中的参数 学习率,权重衰减,冲量(learning_rate , weight_decay , momentum)

无论是深度学习还是机器学习,大多情况下训练中都会遇到这几个参数,今天依据我自己的理解具体的总结一下,可能会存在错误,还请指正. learning_rate , ...

92180
来自专栏C语言及其他语言

【优秀题解】1175:台球碰撞

题号1174,原题见下图: ? 解题思路: 解题思路: 把台球看做质点(台球坐标不变,球桌坐标各个边界向里收缩R,得到新的球桌); 假设没边界,求出小球沿着直...

29660

扫码关注云+社区

领取腾讯云代金券