Codeforces Round #336 Div2 D: Zuma
解法
区間DP。
@mayoko_ 申し訳ねぇ申し訳ねぇ…
[l,r]で回文を挿入しまくって文字列を作りたいです.
a[l]==a[i]のところがあったときそこを使うことにしたとき,[l+1,i-1]と[i+1,r]について考えればOKです
回文が始まるのは長さ1か長さ2でこれを最小化すればOK.
— 高♨級〠焼♨肉 (@camypaper) 2015, 12月 23
コード
#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; }