Codeforces Round #336 Div2 D: Zuma

解法

区間DP。


コード

#include <cstdio>
#include <iostream>
#include <sstream>
#include <fstream>
#include <iomanip>
#include <algorithm>
#include <cmath>
#include <string>
#include <vector>
#include <list>
#include <queue>
#include <stack>
#include <set>
#include <map>
#include <bitset>
#include <numeric>
#include <limits>
#include <climits>
#include <cfloat>
#include <functional>
#include <assert.h>
using namespace std;

typedef long long ll;

vector<int> c;
vector<vector<int>> dp;
int N;
int dfs(int s, int t) {
  if (s == t) return 1;
  if (s + 1 == t) return c[t] == c[s] ? 1 : 2;
  if (dp[s][t] < N) return dp[s][t];

  int ret = dp[s][t];
  if (c[s] == c[t]) ret = min(dfs(s + 1, t - 1), ret);
  ret = min(ret, dfs(s + 1, t) + 1);

  for (int i = s + 1; i < t; ++i) {
    if (c[s] != c[i]) continue;
    if (i == s + 1) {
      ret = min(ret, 1 + dfs(i + 1, t));
    } else {
      ret = min(ret, dfs(s + 1, i - 1) + dfs(i + 1, t));
    }
  }
  dp[s][t] = ret;
  return ret;
}

int main() {
  cin >> N;
  c.assign(N, 0);
  dp.assign(N, vector<int>(N, N));
  for (int i = 0; i < N; ++i) {
    cin >> c[i];
  }
  cout << dfs(0, N - 1) << endl;
}