题目链接 Zuma
区间DP……好奇妙啊……参考了别人的代码……现在都有点糊涂……
#include <bits/stdc++.h> using namespace std; #define rep(i, a, b) for (int i(a); i <= (b); ++i) const int N = 510; int a[N]; int f[N][N]; int n; int dp(int l, int r){ if (~f[l][r]) return f[l][r]; if (l == r) return 1; if (l > r) return 0; int ret = 1 + dp(l + 1, r); rep(i, l + 2, r) if (a[l] == a[i]) ret = min(ret, dp(l + 1, i - 1) + dp(i + 1, r)); if (a[l] == a[l + 1]) ret = min(ret, 1 + dp(l + 2, r)); return f[l][r] = ret; } int main(){ scanf("%d", &n); rep(i, 1, n) scanf("%d", a + i); memset(f, -1, sizeof f); printf("%d\n", dp(1, n)); return 0; }
转载于:https://www.cnblogs.com/cxhscst2/p/6691074.html
