pku 1159 - Standing on Shoulders of Giants

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

#include <iostream>
2

int n;
3

char list[5001]={0};
4

short int dp[5001][5001]={0};
5

int max(int a,int b,int c) {
6

if (b>a) a=b;
7

if (a>c) return a; else return c;
8

}
9

int 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=1; else 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 阅读(204) 评论(0) 编辑收藏引用

随笔档案

只有注册用户登录后才能发表评论。




网站导航: 博客园 IT新闻 BlogJava 知识库博问管理