随笔 - 32  文章 - 2  trackbacks - 0
<2008年11月>
2627282930311
2345678
9101112131415
16171819202122
23242526272829
30123456

常用链接

留言簿(3)

随笔档案

文章档案

搜索

  •  

积分与排名

  • 积分 - 8793
  • 排名 - 1247

最新评论

阅读排行榜

评论排行榜

比较基础的DP,统计字符串正序与逆序的最长公共子序列长度就可以了。
最开始是用Pascal写的,总超时。换C++,根本不需要优化。

 1#include <iostream>
 2int n;
 3char list[5001]={0};
 4short int dp[5001][5001]={0};
 5int max(int a,int b,int c) {
 6    if (b>a) a=b;
 7    if (a>c) return a; else return c;
 8    }

 9int main(){
10    int i,j,k=0;
11    scanf("%d\n",&n);
12    for (i=0;i<n;i++) list[i]=getchar();
13    i=1;
14    for (i=1;i<=n;i++{
15        for (j=1;j<=n;j++{
16         if (list[i-1]==list[n-j]) k=1else k=0;
17         dp[i][j]=max(dp[i-1][j],dp[i][j-1],dp[i-1][j-1]+k);
18         }
 
19    }

20    printf("%d\n",n-dp[n][n]);
21    }
posted on 2008-04-11 21:30 Joseph 阅读(212) 评论(0)  编辑 收藏 引用

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