hdu1159 Common Subsequence--DP
发布日期:2021-10-03 20:31:53
浏览次数:2
分类:技术文章
本文共 1647 字,大约阅读时间需要 5 分钟。
原题链接:
一:原题链接
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 abfcabprogramming contest abcd mnp
Sample Output
420
二:分析理解
给出两个字符串,求两个字符串的最长公共字串。
可以看出:
F[i][j]=F[i-1][j-1]+1;(a[i]==b[j]) F[i][j]=max(F[i-1][j],F[i][j-1]);(a[i]!=b[j])三:AC代码
#include#include #include using namespace std;char a[1001] = "#";char b[1001] = "#";int dp[1005][1005] = { 0 };int main(){ while (~scanf("%s%s", a + 1, b + 1))//加上~,不然超时,醉了 { int a_len = strlen(a) - 1; int b_len = strlen(b) - 1; for (int i = 1; i <= a_len; i++) { for (int j = 1; j <= b_len; j++) { if (a[i] == b[j]) dp[i][j] = dp[i - 1][j - 1] + 1; else dp[i][j] = max(dp[i][j - 1], dp[i - 1][j]); } } printf("%d\n", dp[a_len][b_len]); } return 0;}
转载地址:https://blog.csdn.net/LaoJiu_/article/details/50944094 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2024年04月05日 01时36分24秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
说说 Oracle 的 SYSDATE 函数
2019-04-26
说说 Oracle 的 NVL 与 NVL2 函数
2019-04-26
说说 TCP 协议以及三次握手流程
2019-04-26
说说 Oracle 的 TRUNC 函数
2019-04-26
系统架构设计笔记(41)—— 系统过渡计划
2019-04-26
系统架构设计笔记(42)—— 软件架构概述
2019-04-26
系统架构设计笔记(57)—— 测试自动化与面向对象的测试
2019-04-26
系统架构设计笔记(58)—— 嵌入式系统概论
2019-04-26
说说 Python 的生成器表达式
2019-04-26
说说 Activiti 中的用户与组的概念
2019-04-26
系统架构设计笔记(62)—— 嵌入式数据库管理系统
2019-04-26
系统架构设计笔记(63)—— 实时嵌入式操作系统
2019-04-26
说说如何使用 Canvas 绘制弧线与曲线
2019-04-26
系统架构设计笔记(64)—— 嵌入式系统设计
2019-04-26
系统架构设计笔记(65)—— 项目的范围、时间与成本
2019-04-26
系统架构设计笔记(66)—— 配置管理与文档管理
2019-04-26
说说 Python 元组的高级用法
2019-04-26
系统架构设计笔记(66)—— 配置管理与文档管理
2019-04-26
系统架构设计笔记(67)—— 软件需求管理
2019-04-26