ABS AtCoder - arc085_b（博弈论）

154 阅读 0 评论 102 点赞

我是靠谱客的博主优雅柠檬，这篇文章主要介绍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时，倒数第二个数必然被选择。因此最终的局面只有两种情况：甲直接选择最后一个数，或者两人一人最后一个数，一人倒数第二个数。因为甲有先手权，所以甲可以选择这两种情况中的更优的那个。
简单总结一下，对甲来说比这两种情况更大的你拿不到，更小的你看不上。

复制代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
#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;
}