#2345. 希蒙与蒙蒙选石头
希蒙与蒙蒙选石头
希蒙与蒙蒙选石头
题目背景
蒙蒙经过了一个假期的特训以后,回到了小赛码的基地,她立即拉着希蒙来玩一个游戏...
题目描述
一共有堆石头,由希蒙和蒙蒙依次选择,并且由蒙蒙优先选择。
蒙蒙选择第堆石头可以得到分。
希蒙选择第堆石头可以得到分。
每堆石头只能被取一次。
直到最后一堆石头被取完则游戏结束。
两人都想最大化其分数的差值,即假设蒙蒙的分数为,而希蒙的分数为,对于蒙蒙,她想最大化,而对于希蒙,他想最大化。
两人都绝顶聪明,所以请你输出游戏结束时的值。
输入格式
请注意输入文件名。
第一行一个整数,表示石头的堆数。
接下来一共行,每行两个整数与,含义见上。
输出格式
请注意输出文件名。
你一共需要输出一个整数,含义见上。
样例 #1
样例输入 #1
3
0 2
1 2
3 3
样例输出 #1
1
样例 #2
样例输入 #2
3
1 0
2 3
0 4
样例输出 #2
-1
样例 #3
样例输入 #3
我们提供了三组额外的样例,请参考stone文件夹。
样例输出 #3
我们提供了三组额外的样例,请参考stone文件夹。
提示
数据范围:
对于10%的数据,我们保证。
对于30%的数据,我们保证。
对于100%的数据,我们保证。
相关
在下列比赛中: