付翔的专栏
在鄙视中成长 记录成长的点滴
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 付翔 阅读(1155) 评论(2)  编辑 收藏 引用

FeedBack:
# re: PKU 1159
2009-09-01 16:11 | 凡客诚品
想法是用轮换数组   回复  更多评论
  
# re: PKU 1159
2009-09-06 18:12 | 移动彩铃12530
世界的护肤时间的河佛挡杀佛  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2011年4月>
日一二三四五六
272829303112
3456789
10111213141516
17181920212223
24252627282930
1234567

常用链接

留言簿(2)

随笔分类

随笔档案

文章分类

文章档案

CSDN - 我的blog地址

博客

搜索

  •  

最新评论

阅读排行榜

评论排行榜

Copyright ©2024 付翔 Powered By博客园 模板提供：沪江博客