随笔 - 32  文章 - 2  trackbacks - 0
<2008年4月>
303112345
6789101112
13141516171819
20212223242526
27282930123
45678910

常用链接

留言簿(3)

随笔档案

文章档案

搜索

  •  

积分与排名

  • 积分 - 8798
  • 排名 - 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   知识库   博问   管理