6
Codeforces607B Zuma（区间DP）
source link: https://arminli.com/cf607b/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
Armin's Blog
Codeforces607B Zuma（区间DP）
March 03, 2016
题意：长为 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;
}
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK