ABS AtCoder - arc085_b（博弈论）

本文主要是介绍ABS AtCoder - arc085_b（博弈论），希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

https://atcoder.jp/contests/arc085/tasks/arc085_b?lang=en
在这里插入图片描述
题意：1.初始状态，有N张牌，同时甲乙手中各一张牌，每张牌上有数字。
2.每个回合，先丢掉手中的牌，然后查看牌堆后选择N张牌中的任意前K张牌（1<=K<=N）,同时只保留第K张牌，丢掉其他的牌。
3.甲先手
4.甲要让最终甲乙差的绝对值越大越好，乙要让最终甲乙差的绝对值越小越好。在双方采取最优策略下，求最终的分差绝对值。
思路：显然最后一个肯定选，然后用反证法证明，首先，甲不可能选绝对值最小的数，因为如果选了，乙方会直接选最后的数，乙方同理。按照这个策略，每一轮先手放都会制衡对手，让对手无法选择最后一个数，除了第一轮，甲可以选，最后一轮，玩家被迫选最后一个数。因此N>1时，倒数第二个数必然被选择。因此最终的局面只有两种情况：甲直接选择最后一个数，或者两人一人最后一个数，一人倒数第二个数。因为甲有先手权，所以甲可以选择这两种情况中的更优的那个。
简单总结一下，对甲来说比这两种情况更大的你拿不到，更小的你看不上。

#include <iostream>
typedef long long ll;
using namespace std;
ll a[3000];int main()
{//cout << "Hello world!" << endl;ll N,Z,W;cin>>N>>Z>>W;for(int i=0;i<N;i++){cin>>a[i];}if(N==1){cout<<abs(a[0]-W);return 0;}ll p=a[N-1],q=a[N-2];cout<<max(abs(p-q),abs(p-W))<<endl;return 0;
}