leetcode-go/poj/1390.blocks/main.cc

#include <algorithm>
#include <cstdio>
#include <cstring>

using namespace std;

const int N = 200;
int dp[N][N][N];
// dp[i][j][k] means the highest score for clearing blocks i ~ j.

struct Segment {
  int color;
  int len;
};

Segment seg[N];

// Clear the blocks from i to j, with extra len of block having the same color as seg[j].
int clear(int i, int j, int len) {
  if (dp[i][j][len] != -1) return dp[i][j][len];
  int score = (seg[j].len + len) * (seg[j].len + len);
  if (i == j) return score;
  score += clear(i, j - 1, 0);
  for (int k = i; k + 1 <= j - 1; k++) {
    if (seg[k].color != seg[j].color) continue;
    score = max(score, clear(k + 1, j - 1, 0) + clear(i, k, seg[j].len + len));
  }
  dp[i][j][len] = score;
  return score;
}

int main() {
  int T, n;
  scanf("%d", &T);
  for (int t = 1; t <= T; t++) {
    scanf("%d", &n);
    int cnt = -1, pre = -1;
    for (int i = 0; i < n; i++) {
      int color;
      scanf("%d", &color);
      if (color != pre) {
        seg[++cnt].color = color;
        seg[cnt].len = 1;
        pre = color;
      } else {
        seg[cnt].len++;
      }
    }
    memset(dp, 0xFF, sizeof(dp));
    printf("Case %d: %d\n", t, clear(0, cnt, 0));
  }
  return 0;
}