USACO

USACO 3.3 Home On The Range

Another relatively straightforward DP problem: the basic idea is to calculate the maximum possible squares (land segment that cows can graze on) that each land can expand to, if the given land is considered as the top-left most corner of the square land segment to be expanded. We calculate this information for each land, starting from the right-down most land (which is just itself), then iteratively repeat the calculation until we reach the top-left most corner. During the computation we can also calculate the final answer incrementally.

#include <vector>
#include <iostream>
#include <fstream>

using namespace std;

int N;
vector<vector<int>> dp;
vector<int> ret;

int main() {
    ifstream fin("range.in");
    ofstream fout("range.out");

    fin >> N;
    dp = vector<vector<int>>(N, vector<int>(N, 0));
    ret = vector<int>(N + 1, 0);

    char c;
    for (int i = 0; i < N; ++i) {
        for (int j = 0; j < N; ++j) {
            fin >> c;
            dp[i][j] = c - '0';
        }
    }

    for (int i = N - 2; i >= 0; --i) {
        for (int j = N - 2; j >= 0; --j) {
            if (!dp[i][j]) continue;
            dp[i][j] = std::min(std::min(dp[i][j + 1], dp[i + 1][j]),
                                dp[i + 1][j + 1]) + 1;
            for (int k = 2; k <= dp[i][j]; ++k) {
                ret[k]++;
            }
        }
    }

    for (int i = 2; i < N + 1; ++i) {
        if (!ret[i]) continue;
        cout << i << " " << ret[i] << endl;
        fout << i << " " << ret[i] << endl;
    }
}

USACO

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;
}
USACO

USACO 3.3 Shopping Offers 

#include <vector>
#include <cstring>
#include <iostream>
#include <fstream>
#include <sstream>
#include <unordered_map>

using namespace std;

int dp[6][6][6][6][6];
// 2nd dimension stores the offer price as element 0, (normalized) product
// code as element 1, 2, 3, 4, 5.
vector<vector<int>> offer(106, vector<int>(6, 0));
// Normalize product code to the range of 1-5 inclusive.
unordered_map<int, int> map;
int s;
int totalOffers;
vector<int> buy(vector<int>(6, 0));
int sentinel;

int compute(int a1,int a2, int a3,int a4,int a5){
    if(dp[a1][a2][a3][a4][a5] != sentinel)
        return dp[a1][a2][a3][a4][a5];
    int w1,w2,w3,w4,w5, ret = sentinel;
    for(int i = 1; i <= totalOffers; ++i){
        w1 = a1 - offer[i][1];w2 = a2 - offer[i][2];
        w3 = a3 - offer[i][3];w4 = a4 - offer[i][4];
        w5 = a5 - offer[i][5];
        if(w1 < 0 || w2 < 0 || w3 < 0 || w4 < 0 || w5 < 0) continue;
        if(dp[w1][w2][w3][w4][w5] == sentinel) {
            dp[w1][w2][w3][w4][w5] = compute(w1,w2,w3,w4,w5);
        }
        ret = std::min(ret, dp[w1][w2][w3][w4][w5] + offer[i][0]);
    }
    return ret;
}

int main() {
    ifstream fin("shopping.in");
    ofstream fout("shopping.out");
    fin >> s;
    int n, c, k, b, code = 0;
    for (int i = 1; i <= s; ++i) {
        fin >> n;
        for (int j = 0; j < n; ++j) {
            fin >> c >> k;
            if (map.find(c) == map.end()) {
                map[c] = ++code;
            }
            offer[i][map[c]] = k;
        }
        fin >> offer[i][0];
    }
    
    fin >> b;
    totalOffers = s + b;
    for(int i = 1; i <= b; ++i){
        fin >> c >> k;
        if (map.find(c) == map.end()) {
            map[c] = ++code;
        }
        offer[s + i][map[c]] = 1;
        buy[map[c]] = k;
        fin >> offer[s + i][0];
    }
    
    memset(dp, 0xf, sizeof(dp));
    sentinel = dp[0][0][0][0][0];
    dp[0][0][0][0][0] = 0;
    int ret = compute(buy[1], buy[2], buy[3], buy[4], buy[5]);
    cout << ret << endl;
    fout << ret << endl;
    return 0;
}