付翔的专栏
在鄙视中成长 记录成长的点滴
posts - 106,  comments - 32,  trackbacks - 0


 

#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 付翔 阅读(1113) 评论(2)  编辑 收藏 引用

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

只有注册用户登录后才能发表评论。
【推荐】超50万行VC++源码: 大型组态工控、电力仿真CAD与GIS源码库
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理



<2022年8月>
31123456
78910111213
14151617181920
21222324252627
28293031123
45678910

常用链接

留言簿(2)

随笔分类

随笔档案

文章分类

文章档案

CSDN - 我的blog地址

博客

搜索

  •  

最新评论

阅读排行榜

评论排行榜