 # USACO Gold - Modern Art 3

Hello,

I tried to solve Modern Art 3 here, and here’s my code:

``````// modernArtAgain.cpp : This file contains the 'main' function. Program execution begins and ends there.
//

#include <iostream>
#include <vector>
#include <limits.h>

const int MAX_N = 300;

int dp[MAX_N + 1][MAX_N + 1];

std::vector<int> vect;

int rec(int a, int b) { // range dp from a inclusive to b exclusive
if (dp[a][b] != -1) return dp[a][b]; // if dp[a][b] already defined return it

if (a == b) return dp[a][b] = 0; // if len of substring is 0 return 0
if (a == b - 1) return dp[a][b] = 1; // if len of substring is 1 return 1

if (vect[a] != vect[b - 1]) {
dp[a][b] = 1 + std::min(rec(a, b - 1), rec(a + 1, b)); // if ends are different try removing either one of the ends
}
else {
int first_re;
int last_re;

dp[a][b] = 1 + rec(a + 1, b - 1);

for (first_re = a + 1; first_re < b - 1; ++first_re) {
if (vect[first_re] == vect[a]) dp[a][b] = std::min(dp[a][b], rec(a, first_re + 1) + rec(first_re, b) - 1);
}
// section takes care of cases like 1 2 3 2 1 4 5 4 1, where the ones can be painted with a single stroke

return dp[a][b];
}

int main()
{
int len;
std::cin >> len;
for (int i = 0; i < len; ++i) {
int a;
std::cin >> a;
if (vect.size() == 0 || vect[vect.size() - 1] != a) {
vect.push_back(a);
}
}

for (int i = 0; i < MAX_N + 1; ++i) {
for (int j = 0; j < MAX_N + 1; ++j) {
dp[i][j] = -1;
}
}

std::cout << rec(0, vect.size());
std::cout << "\n";
}