随笔 - 32 文章 - 2 trackbacks - 0

2024年11月

日

一

二

三

四

五

六

常用链接

留言簿(3)

随笔档案

文章档案

2008年4月 (1)

搜索

积分与排名

积分 - 8797
排名 - 1247

阅读排行榜

评论排行榜

pku 1159

比较基础的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 @ 2008-04-11 21:30 Joseph 阅读(212) | 评论 (0) | 编辑收藏

Pascal 与 C++

同样的算法，同样的数据结构，程序的运行效率却差很多。难怪C++会成为主流。
看来有必要好好学习一下C++了。
买了一本《C++ Primer》，够当枕头用的了。再加上一本《算法导论》，天哪何时才能读完？

posted @ 2008-04-04 14:08 Joseph 阅读(102) | 评论 (0) | 编辑收藏

仅列出标题