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;
}
Zhao Li /
Published under (CC) BY-NC-SA in categories 算法  tagged with 动态规划  区间DP