首页 > 其他 > 详细

CodeForces 607B(DP初步_H题)解题报告

时间:2018-01-30 19:04:53      阅读:218      评论:0      收藏:0      [点我收藏+]

题目链接:http://codeforces.com/problemset/problem/607/B

--------------------------------------------------------------------------------

题意:给出一个数字序列,若序列中存在子串存在回文串,可以进行消除,求出最小消除次数。

思路:区间dp,对于区间[i,j],如果a[i]==a[j],那么f[i][j]==f[i+1][j-1],因为区间[i+1,j-1]一定能移除到与边界2个构成回文串,但是要注意,如果区间长度等于2时,f[i][j]等于1并且有状态转移方程f[i][i+len-1]=min(f[i][i+len-1],f[i][k]+f[k+1][i+len-1]) (2<=len<=n,i<=k<i+len-1)

代码:

技术分享图片
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<string>
#include<vector>
#include<stack>
#include<bitset>
#include<cstdlib>
#include<cmath>
#include<set>
#include<list>
#include<deque>
#include<map>
#include<queue>
using namespace std;
typedef long long ll;
const double PI = acos(-1.0);
const double eps = 1e-6;
const int MAXN = 500+10;
int a[MAXN],f[MAXN][MAXN];  
const int INF = 0x3f3f3f3f;
int main(){  
    int n;  
    while(~scanf("%d",&n)){  
        for(int i =0;i<n;i++) scanf("%d",&a[i]);  
        memset(f,INF,sizeof(f));  
        for(int i=0;i<n;i++) f[i][i]=1;
        for(int l=2;l<=n;l++){  
            for(int i=0;i+l-1<n;i++){  
                int j=i+l-1;  
                if(a[i]==a[j]&&l>2) f[i][j]=f[i+1][j-1];
                else if(a[i]==a[j]) f[i][j]=1;  
                for(int k=i;k<j;k++){  
                    f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]);  
  
                }  
            }  
        }  
        printf("%d\n",f[0][n-1]);  
    }  
} 
View Code

 

CodeForces 607B(DP初步_H题)解题报告

原文:https://www.cnblogs.com/caomingpei/p/8386151.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!