Snakes

USACO 2019 US Open Contest, Gold - Problem 1. Snakes

Algorithm

DP on the location in the line where we start, the number of net switches remaining and the current net size.

Given a certain location x, number of switches i, and net size s:

If we have no net size switches left, then the optimal solution is the difference between the net size and the number of snakes at x, plus the optimal solution of the next location with the current net size and zero switches, or dp[x+1][0][s] + diff.
Otherwise, we have two choices:
- Use one net size switch. Then the solution is the minimum of all dp[x+1][i-1] + diff.
- Keep the current number of net size switches. Then the solution is dp[x+1][i-1][s] + diff.

Once we have constructed the DP table, our answer is the minimum of the dp[0][k] (where k is the maximum number of net switches).

C++

#include <bits/stdc++.h>
#include <cstdio>
using namespace std;

void setio(string s) {
    freopen((s+".in").c_str(),"r",stdin);
    freopen((s+".out").c_str(),"w",stdout);
}

int main() {
    int inf = 1e9;
    freopen("snakes.in","r",stdin);
    freopen("snakes.out","w",stdout);

    // Get input
    // setio("snakes");
    int n, k;
    cin >> n >> k;

    vector<int> snakes;
    for (int i=0; i<n; i++) {
        int x;
        cin >> x;
        snakes.push_back(x);
    }

    vector<int> sortedSnakes = snakes;
    sort(sortedSnakes.begin(), sortedSnakes.end());    

    // Tabulation
    /* dp[x][i][s] where
        x is the starting location,
        i is the number of switches,
        s is the current net size
    */
    int dp[401][301][401];
    int minRow[401][301];

    // Fill bottom row
    for (int s=0; s<n; ++s) {
        for (int i=0; i<k+1; ++i) {
            int diff = sortedSnakes[s] - snakes[n-1];
            if (diff >= 0) {
                dp[n-1][i][s] = diff;
            }
            else {
                dp[n-1][i][s] = inf;
            }
        }
    }   
    // Run DP
    for (int x=n-2; x>=0; --x) {
        for (int i=0; i<k+1; ++i) {
            int m = inf;
            for (int j=0; j<n; ++j) {
                if (dp[x+1][i][j] < m) {
                    m = dp[x+1][i][j];
                };
            }
            minRow[x+1][i] = m;
            //cout << m << endl;
        }
        for (int s=0; s<n; ++s) {
            // x = the current location in the line
            // s = the number of net switches remaining
            int diff = sortedSnakes[s] - snakes[x];
            if (diff >= 0) { // Possible to catch snakes with current net
                if (dp[x+1][0][s] != inf) {
                    dp[x][0][s] = dp[x+1][0][s] + diff; // set zero column
                }
                else {
                    dp[x][0][s] = inf;
                }
                for (int i=1; i<=k; ++i) {
                    // switch net, or don't
                    dp[x][i][s] = min(minRow[x+1][i-1], dp[x+1][i][s]) + diff;
                }
            }
            else {
                for (int i=0; i<=k; ++i) {
                    dp[x][i][s] = inf;
                }
            }
        }
    }
    int m = inf;
    for (int j=0; j<n; ++j) {
        if (dp[0][k][j] < m) {
            m = dp[0][k][j];
        }
    }

    cout << m << endl;
    return 0;
}