洛谷 3507 [POI2010]GRA-The Minima Game 题解

发表于 | 更新于 | 阅读次数：
本文字数： 893 字 | 阅读时长 ≈ 3 分钟

题意简述

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

思路

排序，，输出。

具体思路

无脑把数组排序，因为显然答案和给定数字的顺序无关。

其次根据这个推性质。（注意此时我们的已经是从小到大排好序的）。如果我在玩这个的话，那我肯定会取一段连续的出来，否则就会留下一些大的数给对手，无论如何都不划算。连续取的话，则即能保证我的最小值最大，又能保证对面的最大值最小（在取相同数量的情况下）。但是数量多少，就是我们决策的一个关键点。

关于决策：一看就知道是（因为不会做，又和决策有关，所以考虑瞎jb）。

设表示我们考虑排好序的中前个数的最优答案（就是轮流取数后的最大差值）。
那么首先我们要枚举上一个人走在了那里，设为。那么由方程：。注意，这里的先后手不是绝对的，是相对的。也就是时候，我们在考虑的时候，是先手-后手的答案，但是是后手-先手的答案。而我们要求a[j]+先手-后手，所以转移方程式应该是a[j]-dp[j-1]，即a[j]-(后手-先手)，即a[j]+先手-后手。

然后我们发现这转移是的。但是的值是固定的，所以我们珂以用前缀和优化来优化这个题。

然后我们发现，我们算需要用到个状态，然后需要用到个状态。其中有个状态是共有的，表达式都一样，而且值也没有改变。所以我们干脆就直接继承的答案好了，然后多把的答案给算上，求个即珂。

转移方程变为：。

实现注意

需要呢！！！

代码：

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
#include<bits/stdc++.h>
using namespace std;
namespace Flandre_Scarlet
{
	#define N 1666666
	#define int long long 
	#define F(i,l,r) for(int i=l;i<=r;++i)
	#define D(i,r,l) for(int i=r;i>=l;--i)
	#define Fs(i,l,r,c) for(int i=l;i<=r;c)
	#define Ds(i,r,l,c) for(int i=r;i>=l;c)
	#define Tra(i,u) for(int i=G.Start(u),__v=G.To(i);~i;i=G.Next(i),__v=G.To(i))
	#define MEM(x,a) memset(x,a,sizeof(x))
	#define FK(x) MEM(x,0)
	int n,a[N];
	void R1(int &x)
	{
	    x=0;char c=getchar();int f=1;
	    while(c<'0' or c>'9') f=(c=='-')?-1:1,c=getchar();
	    while(c>='0' and c<='9') x=(x<<1)+(x<<3)+(c^48),c=getchar();
	    x=(f==1)?x:-x;
	}
	void Input()
	{
		R1(n);
		F(i,1,n) R1(a[i]);
	}

	int dp[N];
	void Soviet()
	{
		sort(a+1,a+n+1);
		F(i,1,n)
		{
			dp[i]=max(dp[i-1],a[i]-dp[i-1]);
		}
		printf("%lld\n",dp[n]);
	}
	void IsMyWife()
	{
		Input();
		Soviet();
	}
	#undef int //long long 
}
int main()
{
	Flandre_Scarlet::IsMyWife();
	getchar();getchar();
	return 0;
}
w