posts - 106, comments - 32, trackbacks - 0

PKU 1159

#include<stdio.h>

char str[5001];

short int data[5005][5005] = {0};//这里用int 会超内存

int main()

{

int len;

long max = 0,i ,j;

scanf("%d%s",&len,str);

//len = strlen(str1);

for(i = 0;i < len ;i++)

{

for(j = 0;j< len-i;j++)

{

if(i == 0)

data[j][j+1] = 0;

else if(i == 1)

{

if(str[j] == str[j+1])

data[j][j+i] = 0;

else

data[j][j+i] = 1;

}

else

{

if(str[j] == str[j+i])

data[j][j+i] = data[j+1][j+i-1];

else

data[j][j+i] = (data[j][j+i-1]<data[j+1][j+i]?data[j][j+i-1]:data[j+1][j+i]) + 1;

}

printf("%d",data[0][len-1]);

return 0;

}

简单的DP 从长度为一开始到 len 一步一步过来最后得到结果既是

还有一个想法是用轮换数组

posted on 2009-09-01 10:39 付翔阅读(1146) 评论(2) 编辑收藏引用

FeedBack:

# re: PKU 1159

2009-09-01 16:11 | 凡客诚品

想法是用轮换数组回复更多评论

# re: PKU 1159

2009-09-06 18:12 | 移动彩铃12530

世界的护肤时间的河佛挡杀佛回复更多评论

刷新评论列表

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




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

2009年9月

日

一

二

三

四

五

六

常用链接

留言簿(2)

随笔分类

随笔档案

文章分类

web (2)

文章档案

CSDN - 我的blog地址

我在CSDN的博客

常用链接

留言簿(2)

随笔分类

随笔档案

文章分类

文章档案

CSDN - 我的blog地址

博客

搜索

最新评论

阅读排行榜

评论排行榜