abc078d <博弈>-526互联

D - ABS
// https://atcoder.jp/contests/abc078/tasks/arc085_b
// <博弈>
// 思路:
// 首先注意到两点:
//  1. a[n] 一定会是游戏结束时某个人的数字
//  2. 对于先手, 他可以直接导致两种确定的游戏结果
//      1. a[n], w  (先手选择 a[n], 游戏结束)
//      2. a[n-1], a[n]  (先手选择a[n-1], 后手只能选择a[n], 游戏结束)
//      因而先手可选择这两种游戏结果中的较优者
// 而后需要考虑, 先手是否可能选择 a[1~n-2] ? (因为这样的选择, 游戏结果并不会完全受先手者控制)
// 即, 思考先手选择 a[1~n-2], 是否会得到比上述的两种确定的游戏结果更优的结果 ?
// 换位思考, 如果先手A确实选择了a[1~n-2]中一个数(比如a[i]), 那么后手B的最优策略是如何行动 ?
// 因为AB两人完全利益冲突, 如果B的选择中存在会导致游戏结果值比 abs(a[n-1] - a[n]) 更大的数(对A有利)
//  那么此时B一定会选择拿走a[n-1], 使得A不得不选择a[n], 此时游戏结果不会比 abs(a[n-1] - a[n])更大,
//  因此, A尽可能选择最开始提到的两种确定的游戏结果中的较优者(本游戏结果仅与a[n-1] a[n] z w 四个数有关)
// 总结:
// 1. 当下可确定达到的最优情况
// 2. 换位思考
// 3. 递归思考 思考当前情况的先后手, 而不是具体的AB人
#include <iostream>
#include <algorithm>
#include <vector>
#include <cstring>
using namespace std;
using LL = long long;
const int N = 2010;
int a[N];

void solv()
{
    int n, z, w;
    cin >> n >> z >> w;
    for (int i = 1; i <= n; i ++) cin >> a[i];
    int ans = abs(a[n] - w);
    if (n > 1) ans = max(ans, abs(a[n-1] - a[n]));
    cout << ans << endl;
}

int main()
{
    ios::sync_with_stdio(false); cin.tie(0); cout.tie(0);
    int T = 1;
	// cin >> T;
    while (T --)
    {
        solv();
    }
    return 0;
}
078d
abc