The Collection Caper - BIO 2024 Round 2

/**
 * @file caper.cpp
 * @version 1.0
 * @date 2024-04-03
 *
 * usage:
 *      Read from / write to default input.txt and output.txt
 *          caper.exe
 *      Read from / write to custom files:
 *          caper.exe in.txt out.txt
 */
#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

void fileIO(int argc, char *argv[]);

const int INF = 1e5;

int minMovesToErase(vector<int> v) {
    int n = v.size();

    vector<vector<int>> dp(1+n, vector<int>(1+n));
    v.push_back(0);
    /*
    dp[l][r] is the minimum number of moves to erase the range v[l], v[l+1], ..., v[r-1]
    (excluding r), given that only elements from the same collection as v[r] can remain
    */

    /*
    It can be shown that for any block of values from the same collection that are initially
    consecutive, it can be shown that all optimal solutions will erase them all in one step.
    I use this to slightly simplify the code, though the main concept of the solution does not
    depend on it.
    */

    for (int sz = 1; sz <= n; ++sz) {
        for (int l = 0; l+sz <= n; ++l) {
            int r = l+sz;
            dp[l][r] = INF;
            int canLeave = v[r];

            // case: do not erase the first element
            if (v[l] == canLeave) dp[l][r] = min(dp[l][r], dp[l+1][r]);

            // case: erase the first element

            int firstBlockR = l;
            while (firstBlockR < r && v[firstBlockR] == v[l]) ++firstBlockR;
            //  subcase: erase the first element in its own block (if the block size is >= 2)
            if (firstBlockR-l >= 2) dp[l][r] = min(dp[l][r], 1 + dp[firstBlockR][r]);

            //  subcase: erase the first element along with another block
            for (int i = firstBlockR, lastDifferent = firstBlockR; i < r; ++i) {
                if (v[i] == v[l] && (i+1 == r || v[i+1] != v[l])) { // a block with from the same collection as v[l] ends at i
                    int lastBlockL = lastDifferent+1, lastBlockR = i+1;
                    dp[l][r] = min(dp[l][r], 1 + dp[firstBlockR][lastBlockL] + dp[lastBlockR][r]);
                } else if (v[i] != v[l]) lastDifferent = i;
            }
        }
    }
    return dp[0][n];
}

int main(int argc, char *argv[]) {
    fileIO(argc, argv); // remove for standard input/output

    int n; cin >> n;
    vector<int> a(n);
    for (int &x : a) cin >> x;
    cout << minMovesToErase(a) << '\n';
    return 0;
}

void fileIO(int argc, char *argv[]) {
    const char * in = "input.txt", * out = "output.txt";
    if (argc > 1) in = argv[1];
    if (argc > 2) out = argv[2];
    freopen(in, "r", stdin);
    freopen(out, "w", stdout);
}