D - ABS AtCoder Regular Contest 085

D - ABS

問題概略　

N枚のカードの山がある。プレイヤーが二人いて最初にz,wを持っている。

お互いに山札から1枚以上のカードを引き、最後に引いたカードを手札にする。

先行はお互いの差の絶対値を最大化、後攻は最小化する時のスコアはいくつか。

制約

• 入力は全て整数
• $1\le N\le 2000$
• $1\le Z,W,a_i\le {10}^9$

解法

O(1)で解けるらしいですね、でもdpで解きます

残りの山札がi枚なら、相手はan-iのカードを持っているためその範囲での最善手がわかる。

残り枚数＋＋でループを回し、先行と後攻でそれぞれの最善手のスコアを書いていけばN^2で求まる。

類題

B: ゲーム - Typical DP Contest | AtCoder

public static void main(String[] args)
    {
        //longを忘れるなオーバーフローするぞ
        N = sc.nextInt();
        int z = sc.nextInt();
        int w = sc.nextInt();
        A = sc.nextIntArray(N);
        int[] dpx = new int[N + 1];//山札の残り枚数i スコア
        int[] dpy = new int[N + 1];//山札の残り枚数
        for (int i = 1; i < N + 1; i++)
        {
            //x 最大化する
            dpy[0] = Math.abs((i == N ? w : A[N - i - 1]) - A[N - 1]);
            for (int j = i - 1; j >= 0; j--)
            {
                dpx[i] = Math.max(dpx[i], dpy[j]);
            }
            //y 最tiisa化する
            dpx[0] = Math.abs((i == N ? z : A[N - i - 1]) - A[N - 1]);
            dpy[i] = INF;
            for (int j = i - 1; j >= 0; j--)
            {
                dpy[i] = Math.min(dpy[i], dpx[j]);
            }

        }
        System.out.println(dpx[N]);
    }