BZOJ 2091 [Poi2010]The Minima Game

作者: MayFlyyh 分类: DP 发布时间: 2018-09-20 18:23 ė 6 没有评论

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

本文出自MayFlyyh's Blog,转载时请注明出处及相应链接。

本文永久链接: http://www.mayflyyh.com/archives/347

0

发表评论

电子邮件地址不会被公开。

Ɣ回顶部