周赛F题 POJ 1458(最长公共子序列)
2024-10-19 22:29:30
F - F
Time Limit:1000MS Memory Limit:10000KB 64bit IO Format:%I64d & %I64u
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, x ij = 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.
Input
The program input is from the std input. Each data set in the input contains two strings representing the given sequences. The sequences are separated by any number of white spaces. The input data are correct.
Output
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理解不够。
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
char a[],b[];
int dp[][];
int main()
{
while(scanf("%s %s",a,b)!=EOF)
{
int x=strlen(a);
int y=strlen(b);
for(int i=;i<=x;i++)
{
for(int j=;j<=y;j++)
{
if(a[i-]==b[j-])
dp[i][j]=dp[i-][j-]+;
else
dp[i][j]=max(dp[i-][j],dp[i][j-]);
}
}
cout<<dp[x][y]<<endl;
}
return ;
}
最新文章
- 文本选择问题: css &; js
- [转] Oracle sql 查询突然变慢 -- 案例分析
- Python基础2- Hello,world
- 临床试验中PI、CI、SI、COI是指哪些人?
- 使用PreTranslateMessage替代钩子函数处理键盘消息
- 用issnode+IIS来托管NodeJs Server
- 利用less监视模式实时预览样式刷新浏览器
- onclick事件对动态参数类型为字符串的处理
- JS的文本编辑框jwysiwyg-0.6
- 深入理解ThreadLocal(二)
- php中error_report函数的含义及各参数含义
- 调试postgresql9.5.2最新源码
- NFC扫描
- ADO面板上的控件简介
- 微软sqlHelper
- java基础(一)面向对象
- Linux kernel的中断子系统之(四):High level irq event handler
- Git 经常用到的命令
- MySQL中间件之ProxySQL(15):ProxySQL代理MySQL组复制
- C# WINFORM 应用程序动态读写xml config文件,获取数