Mayflyyh
Mayflyyh
MayFlyyh's Blog
BZOJ 2091 [Poi2010]The Minima Game

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

Input
第一行一个正整数N (N <= 1,000,000),第二行N个正整数(不超过10^9)。

Output
一个正整数,表示最终A与B的分差。

Sample Input
3
1 3 1

Sample Output
2

HINT
第一次A取走3,第二次B取走两个1,最终分差为2。


。。如果从大到小排序,那每次从大到小拿,但并不确定拿多少能最优,所以采取倒着做的方法

从小到大排序

F[i]=min(F[i-1],a[i]-F[i-1])

要么是把对方的状态变成自己的,要么是取第i个,看那个最大就行了,无后效性。

#include<bits/stdc++.h>
const int N = 1020000;
int a[N],n;
int F[N];
int read(){
    int x=0,fl=1;char c=getchar();
    if(!isdigit(c)){if(c=='-')fl*=-1;c=getchar();}
    while(isdigit(c)){x=(x<<3)+(x<<1)+c-'0';c=getchar();}
    return fl*x;
}
int main(){
    n=read();
    for(int i=1;i<=n;++i) a[i]=read();
    std::sort(a+1,a+1+n);
    F[1]=a[1];
    for(int i=2;i<=n;++i){
        F[i]=std::max(F[i-1],a[i]-F[i-1]);
    }
    printf("%d",F[n]);
    return 0;
}

a+b=c

本文链接:http://www.mayflyyh.com/archives/347
知识共享许可协议
本文采用CC BY-NC-SA 3.0进行许可。
首页      DP      BZOJ 2091 [Poi2010]The Minima Game
http://0.gravatar.com/avatar/6cc3a2831375e487976e09c80dfcb52e?s=256&d=monsterid&r=g

MayFlyyh

文章作者

Oier

发表评论

textsms
account_circle
email

Captcha Code

MayFlyyh's Blog

BZOJ 2091 [Poi2010]The Minima Game
Description 给出N个正整数,AB两个人轮流取数,A先取。每次可以取任意多个数,直到N个数都被取走。 每次获得的得分为取的数中的最小值,A和B的策略都是尽可能使得自己的得分减去对手…
扫描二维码继续阅读
2018-09-20