1114D - Flood Fill - CodeForces Solution

#include <iostream>
#include <string>
#include <memory.h>
#include <vector>
#include <algorithm>
#include <math.h>
#include <set>
#include <map>
#include <stack>
#include <queue>
#include <unordered_set>
#include <unordered_map>
#include <functional>
#include <numeric>
#include <list>

using namespace std;

using PII = pair<int, int>;
using PLL = pair<long long, long long>;

void Input(int *arr, int size) {
    for (int i = 0; i < size; ++i) {
        cin >> arr[i];
    }
    return;
}

void FloodFill() {
    int size1;
    cin >> size1;
    int color1[size1];
    Input(color1, size1);
    basic_string<int> color2;
    for (int i = 0; i < size1; ++i) {
        int idx = i;
        while (idx < size1 && color1[idx] == color1[i]) { idx++; }
        color2.push_back(color1[i]);
        i = idx - 1;
    }
    int size2 = color2.size(), dp[size2][size2][2];
    for (int i = size2 - 1; i >= 0; --i) {
        dp[i][i][0] = dp[i][i][1] = 0;
        for (int j = i + 1; j < size2; ++j) {
            dp[i][j][0] = min(dp[i + 1][j][0] + (color2[i] == color2[i + 1] ? 0 : 1),
                dp[i + 1][j][1] + (color2[i] == color2[j] ? 0 : 1));
            dp[i][j][1] = min(dp[i][j - 1][0] + (color2[j] == color2[i] ? 0 : 1),
                dp[i][j - 1][1] + (color2[j] == color2[j - 1] ? 0 : 1));
        }
    }
    cout << min(dp[0][size2 - 1][0], dp[0][size2 - 1][1]) << endl;
    return;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    cout.tie(nullptr);
    int testcase = 1;
    //cin >> testcase;
    while (testcase--) {
        FloodFill();
    }
    return 0;
}