pku1159_DP - wyiu - C++博客

C++博客 :: 首页 :: 新随笔 :: 联系 :: 聚合

:: 管理

posts - 100, comments - 15, trackbacks - 0

pku1159_DP

#include<iostream>
2

using namespace std;
3

#define MAX 5000
4

char str[MAX+2];
6

char re_str[MAX+2];
7

//int res[MAX+1][MAX+1]; //MLE
8

int res[2][MAX+1];
9

int n;
10

void dp()
12

{
13

int i,j;
14

for(j=0;j<=n;j++)
15

res[0][j]=j;
16

res[1][0]=1;
17

for(i=1;i<=n;i++)
18

{
19

res[i%2][0]=i;
20

for(j=1;j<=n;j++)
21

{
22

if(str[i]==re_str[j])
23

res[i%2][j]=res[(i-1)%2][j-1];
24

else{
25

res[i%2][j]=min(res[(i-1)%2][j],res[i%2][j-1])+1;
26

}
27

}
28

}
29

}
30

int main()
31

{
32

int i;
33

scanf("%d",&n);
34

for(i=1;i<=n;i++)
35

{
36

scanf(" %c",&str[i]);
37

re_str[n-i+1]=str[i];
38

}
39

dp();
40

printf("%d\n",res[n%2][n]>>1);
41

return 0;
42

}

posted on 2009-05-10 14:38 wyiu 阅读(185) 评论(0) 编辑收藏引用所属分类: POJ

只有注册用户登录后才能发表评论。
【推荐】100%开源！大型工业跨平台软件C++源码提供，建模，组态！

相关文章: poj 1061 线性同余 poj 2115 线性同余 poj 3368 rmq(st) poj 3264 RMQ poj 2352 树状数组 poj 1469 二分匹配 poj 2186 有向图强连通分支 poj 2239 二分图最大匹配 poj 3748 位运算 poj 2724 二分匹配

网站导航: 博客园 IT新闻 BlogJava 博问 Chat2DB 管理

常用链接

留言簿(1)

随笔分类(84)

随笔档案(100)

向高手学习

搜索

积分与排名

最新评论

阅读排行榜

评论排行榜