hdoj 1159 Common Subsequence【LCS】【DP】
2024-08-25 22:24:29
Common Subsequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 28494 Accepted Submission(s): 12735
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.
..., 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
非常基础的一道LCS。以下给出第一种情况的DP路线,例如以下图。
希望能够帮助大家。
AC代码:
#include<stdio.h>
#include<string.h>
#define max(a,b) (a>b? a:b)
char a[1000],s[1000];
int dp[1000][1000];
int main()
{
int i,j,k;
while(scanf("%s%s",a,s)!=EOF)
{
memset(dp,0,sizeof(dp));
int l=strlen(a);
int le=strlen(s);
for(i=1;i<=l;i++)
{
for(j=1;j<=le;j++)
if(a[i-1]==s[j-1])//推断左側和上側字符是否相等
dp[i][j]=dp[i-1][j-1]+1;//把左上側的dp值+1
else
dp[i][j]=max(dp[i-1][j],dp[i][j-1]);//取左側或上側的最大dp值
}
printf("%d\n",dp[l][le]);
}
return 0;
}
最新文章
- RabbitMq 集群搭建
- JQuery选择器JQuery 事件
- LinkedList
- 设计winform自带动态加载工具按钮和实现热键响应
- exgcd,求乘法逆元
- C# virtual和abstract的
- 完美解决IE6不支持position:fixed的bug
- git无法连接bitbucket/github时,出现";Permission deied(publickey)";
- iOS数据持久化存储:归档
- 小qyvlik 先看两个视频,和 QtQuick UI 问答
- win7 下面使用任务计划程序执行php脚步
- servlet三种实现方式之三通过继承HttpServlet开发servlet
- Oracle常用语句记录
- CSS传统布局之布局模型
- [HDUOJ1312]Red And Black (经典的DFS)
- php gif处理
- spring开启事务时启动报错SAXParseException
- Redhat 简单本地yum 配置
- WPF Demo13通知项属性+数据绑定(代码层)
- 用bayes公式进行机器学习的经典案例