Codeforces607B Zuma（区间DP）

题目链接

题意：长为 n 的序列，每次可以删除一个回文子串，删除之后两边合并起来，问最少几次可以将序列删完。

dp[l][r] 表示[l, r]区间内最少次数，s[l] ==s[r]时，dp[l][r] = dp[l+1][r-1]。

#include<cstring>
#include<cstdio>
#include<cstring>
#include<cmath>
#include<string>
#include<iostream>
#include<algorithm>
using namespace std;
int dp[505][505];
int s[505];

int solve(int l, int r){
    if(l == r) return 1;
    if(l > r) return 0;
    if(dp[l][r] > 0) return dp[l][r];
    int ret = 505;
    for(int i = l; i < r; i++){
        ret = min(ret, solve(l, i)+solve(i+1, r));
    }
    if(s[l] == s[r])
        ret = min(ret, max(1, solve(l+1, r-1)));
    dp[l][r] = ret;
    return ret;
}

int main(){
    //freopen("a.txt", "r", stdin);
    int n;
    while(scanf("%d", &n) != EOF){
        memset(dp, 0, sizeof(dp));
        for(int i = 1; i <= n; i++)
            scanf("%d", &s[i]);
        cout << solve(1, n) << endl;
    }
    return 0;
}