注册 登录  
 加关注
   显示下一条  |  关闭
温馨提示!由于新浪微博认证机制调整,您的新浪微博帐号绑定已过期,请重新绑定!立即重新绑定新浪微博》  |  关闭

告别迷茫

梦想与现实的差距,就是我们生活的意义。因为我们有差距,我们才会一直积累,在努力。

 
 
 

日志

 
 

hdu 1159 最长公共子序列  

2014-03-20 21:36:55|  分类: DP |  标签: |举报 |字号 订阅

  下载LOFTER 我的照片书  |

 1 26

 f a
 a 11 1 1
 b 1 2 2 2
 c0 1 2 2 33
 f 0 1 2 3
 b 0 1 2 3
   
   

Common Subsequence

Time
Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K
(Java/Others)
Total Submission(s): 20537    Accepted Submission(s):
8822



Problem Description

A subsequence of a given sequence is the given sequence
with some elements (possible none) left out. Given a sequence X = <x1, x2,
..., xm> another sequence Z = <z1, z2, ..., zk> is a subsequence of X
if there exists a strictly increasing sequence <i1, i2, ..., ik> of
indices of X such that for all j = 1,2,...,k, xij = zj. For example, Z = <a,
b, f, c> is a subsequence of X = <a, b, c, f, b, c> with index sequence
<1, 2, 4, 6>. Given two sequences X and Y the problem is to find the
length of the maximum-length common subsequence of X and Y.
The program
input is from a text file. Each data set in the file contains two strings
representing the given sequences. The sequences are separated by any number of
white spaces. The input data are correct. For each set of data the program
prints on the standard output the length of the maximum-length common
subsequence from the beginning of a separate line.

 


Sample Input

abcfbc abfcab
programming contest
abcd mnp

 


Sample Output

4
2
0

 


Source


 


Recommend

Ignatius   |   We have carefully selected several
similar problems for you:  1087 1176 1003 1058 1069 

#include<stdio.h>
#include<string.h>


char a[2014];
char b[2014];
int dp[2014][2014];
int max(int x,int y)
{
return x>y?x:y;
}


int main()
{
int i,j;
while(scanf("%s %s",a,b)!=EOF)
{
int len1=strlen(a);
int len2=strlen(b);
for(i=0;i<len1;i++)
{
dp[i][0]=0;
}
for(i=0;i<len2;i++)
{
dp[0][i]=0;
}
for(i=1;i<=len1;i++)
{
for(j=1;j<=len2;j++)
{
if(a[i-1]==b[j-1])
{
dp[i][j]=dp[i-1][j-1]+1;//相同的必然会相加1;
}
else
{
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);//不同的比较自己的十字架的两边
}

}
}

printf("%d\n",dp[len1][len2]);//可一通过自己的计算把最大的必然是最后二维数组的元素;

}
return 0;
}


 


  评论这张
 
阅读(0)| 评论(0)
推荐 转载

历史上的今天

在LOFTER的更多文章

评论

<#--最新日志,群博日志--> <#--推荐日志--> <#--引用记录--> <#--博主推荐--> <#--随机阅读--> <#--首页推荐--> <#--历史上的今天--> <#--被推荐日志--> <#--上一篇,下一篇--> <#-- 热度 --> <#-- 网易新闻广告 --> <#--右边模块结构--> <#--评论模块结构--> <#--引用模块结构--> <#--博主发起的投票-->
 
 
 
 
 
 
 
 
 
 
 
 
 
 

页脚

网易公司版权所有 ©1997-2017