心如止水
Je n'ai pas le temps
posts - 400,comments - 130,trackbacks - 0

经典的动态规划题。

d[i][j]表示把从1..ij..n变成回文词最少需要的字符个数。

则:d[i][j]=min(d[i][j],d[i-1][j+1]) s[i]==s[j]

d[i][j]=min(d[i][j],d[i-1][j]+1)

    d[i][j]=min(d[i][j],d[i][j+1]+1)

以下是我的程序:

#include<stdio.h>
#define maxn 5005
#define maxint 20000
#define min(a,b) (a<b?a:b)
char ch,s[maxn]={0};
short i,j,n,ans,d[maxn][maxn];
int main()
{
    freopen(
"palin.in","r",stdin);
    freopen(
"palin.out","w",stdout);
    scanf(
"%ld\n",&n);
    
for(i=1;i<=n;i++)
      scanf(
"%c",&s[i]);
    
for(i=0;i<=n+2;i++)
      
for(j=0;j<=n+2;j++)
        d[i][j]
=maxint;
    
// Init
    d[0][n+1]=0;
    d[
0][n]=1;
    d[
1][n+1]=1;
    
// 边界 
    for(i=1;i<=n+1;i++)
      
for(j=n+1;j>=i;j--)
      
{
         
if(s[i]==s[j])
           d[i][j]
=min(d[i][j],d[i-1][j+1]);
         d[i][j]
=min(d[i][j],d[i-1][j]+1);
         d[i][j]
=min(d[i][j],d[i][j+1]+1);
      }

    
// DP
    ans=maxint;
    
for(i=1;i<=n;i++)
    
{
       ans
=min(ans,d[i][i]);
       ans
=min(ans,d[i][i+1]);
    }

    
// Find Answer
    printf("%d\n",ans);
return 0;
}

posted on 2010-01-06 20:05 lee1r 阅读(304) 评论(0)  编辑 收藏 引用 所属分类: 题目分类:动态规划

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理