HDU 1159 最长公共子序列
2024-09-01 20:59:03
Common Subsequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 53443 Accepted Submission(s): 24607
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.
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 abfcabprogramming contestabcd mnp
Sample Output
420
【题意】
一个给定序列的子序列是一个给定序列,其中有些元素(可能没有)被省略。给定一个序列 X = <x1, x2, ..., xm> 另一个序列 Z = <z1, z2, ..., zk> 是X的子序列,如果存在严格递增序列, <i1, i2, ..., ik> 对所有 j = 1,2,…,k, xij = zj。例如,Z = <a, b, f, c> 是 X = <a, b, c, f, b, c> 的子序列,索引序列< 1,2,4,6 >。给定两个序列X和Y,问题是求X和Y的最大长度公共子序列的长度。
序列由任意数量的空格分隔。输入数据是正确的。对于每组数据,程序在标准输出上打印从单独行开始的最大长度公共子序列的长度。
注意:最长公共子序列 ,可以不连续。
【代码】
#include<bits/stdc++.h>
#define MAX 5005
using namespace std;
int f[MAX][MAX];
string s,t;
int main(){
while(cin>>s>>t){
for(int i=;i<=s.length();i++)
for(int j=;j<=t.length();j++){
f[i][j]=max(f[i-][j],f[i][j-]);
if(s[i-]==t[j-])
f[i][j]=max(f[i][j],f[i-][j-]+);
}
cout<<f[s.length()][t.length()]<<endl;
}
return ;
}
最新文章
- socket学习之聊天室
- Jmeter之Bean shell使用(二)
- Hadoop: MapReduce2的几个基本示例
- Effective Objective-C 2.0 — 第二条:类的头文件中尽量少引入其他头文件
- 【9-6】Centos学习笔记
- (转)大数据时代下的SQL Server第三方负载均衡方案----Moebius测试
- zoj 3644(dp + 记忆化搜索)
- var 和 dynamic在实际项目中的应用
- Perl的DATA文件句柄
- 1106. Two Teams(dfs 染色)
- java中实现多态的机制是什么?
- Jquery使用tbody编辑功能实现table输入计算功能
- C语言开发面试题
- STM32f4 ARM Bootloader
- angular路由模块(二)
- C语言的第一次作业总结
- docker 安装 mongodb
- SQL 事务 begin tran、commit tran、rollback tran 的用法
- mysql 查询 所有 父节点 单表
- A1043 Is It a Binary Search Tree (25 分)