USACO 3.3 A Game

Typical dynamic programming problem. The search space is the optimal value player A could get at a given play step. A play step can be identified by the current state of the board - namely the unused board which is marked by the starting (left) and ending (right) indices. Let’s denote the start index as a, end index as b, and denote dp[a][b] as the optimal value player A could get.

Next we need find out the state transfer function. Since player B will also play optimally (that is, player B is as smart as player A, and both players will try use same optimal strategy to win the game), we can have the transfer function like this:

$f(a, b) = \begin{cases}0 & a > b \\
max(f(a) + min(f(a + 2, b), f(a + 1, b - 1)), f(b) + min(f(a, b - 2), f(a + 1, b - 1) & a \le b \\
\end{cases}$

And this could be calculated recursively (from two ends of board to middle).

#include <vector>
#include <iostream>
#include <fstream>
#include <sstream>
#include <numeric>

using namespace std;

int N;
vector<int> board;
vector<vector<int>> dp;

int compute(int a, int b) {
    if (a > b) return 0;
    if (dp[a][b] == -1) {
        dp[a][b] = std::max(board[a] + std::min(compute(a + 2, b),
                                                compute(a + 1, b - 1)),
                            board[b] + std::min(compute(a, b - 2),
                                                compute(a + 1, b - 1)));
    }
    return dp[a][b];
}

int main() {
    ifstream fin("game1.in");
    ofstream fout("game1.out");
    fin >> N;
    board = vector<int>(N, 0);
    dp = vector<vector<int>>(N, vector<int>(N, -1));
    for (int i = 0; i < N; ++i) {
        fin >> board[i];
    }
    int sum = std::accumulate(board.begin(), board.end(), 0);
    int p1 = compute(0, N - 1);
    int p2 = sum - p1;
    cout << p1 << " " << p2 << endl;
    fout << p1 << " " << p2 << endl;
}