最长公共子序列-Hdu1159
2024-09-03 22:47:44
Common Subsequence
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/32768 K (Java/Others)
Total Submission(s): 57902 Accepted Submission(s): 26737
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 abfcab
programming contest
abcd mnp
Sample Output
4
2
0
理解题意:
首先我们的了解什么是子序列,一个给定序列的子序列是在该序列中删去若干元素后的得到的序列,可以是不连续的。
做题思路:
找到两个序列的最长公共子序列,用最基础的DP模板即可
代码:
#include <bits/stdc++.h> using namespace std; int dp[][];
string str1,str2; int LCS(){
for(int i = ;i < str1.length(); i++){
for(int j = ;j < str2.length(); j++){
if(str1[i] == str2[j])
dp[i+][j+] = dp[i][j] + ;
else
dp[i+][j+] = max(dp[i][j+],dp[i+][j]);
}
}
return dp[str1.length()][str2.length()];
} int main()
{
while(cin>>str1>>str2){
cout<<LCS()<<endl;
}
return ;
}
最新文章
- Bzoj4008 [HNOI2015]亚瑟王
- ubuntu下设置数据库字符集
- 删除sde用户问题
- iOS开发~UI布局(一)初探Size Class
- android 单选、多选弹出菜单
- 一个页面多Table多分页的问题
- ios数据库FMDB
- android内存优化发展——使用软引用
- org.springframework.beans.BeanUtils
- Angulajs 定时器使用
- SQL常规查询详解
- [iOS Animation]-CALayer 视觉效果
- python 最佳实践与资源汇总
- Python程序员去上海工作有多难?
- 关于Unity里动态加载图片
- 利用 Python + Selenium 实现对页面的指定元素截图(可截长图元素)
- C# 程序异常关闭时的捕获
- Vue Document
- Java 存储时间戳的几种方式
- vi 复制或剪切多行超级强大方法