POJ2250 Compromise(dp)_poj2250:compromise-程序员宅基地

给出两段字符串数组, 每段以"#"结尾, 要求输出两段字符串数组最长的公共字符串.

lcs题目, 增加了一个flag数组保存字符串比较结果, 用于最后递归数据答案.

AC代码:

#include "iostream"
#include "cstdio"
#include "cstring"
#include "algorithm"
using namespace std;
const int MAXN = 105;
char s1[MAXN][MAXN], s2[MAXN][MAXN];
int dp[MAXN][MAXN], flag[MAXN][MAXN], len1, len2;
void lcs()
{
	for(int i = 1; i <= len1; ++i)
		for(int j = 1; j <= len2; ++j) {
			if(strcmp(s1[i - 1], s2[j - 1]) == 0) {
				dp[i][j] = dp[i - 1][j - 1] + 1;
				flag[i][j] = 1;
			}
			else {
				if(dp[i - 1][j] >= dp[i][j - 1]) {
					flag[i][j] = 2;
					dp[i][j] = dp[i - 1][j];
				}
				else {
					flag[i][j] = 3;
					dp[i][j] = dp[i][j - 1];
				}
			}
		}
}
void print(int x, int y)
{
	if(!x || !y) return;
	if(flag[x][y] == 1) {
		print(x - 1, y - 1);
		printf("%s ", s1[x - 1]);
	}
	else if(flag[x][y] == 2) print(x - 1, y);
	else print(x, y - 1);
}
int main(int argc, char const *argv[])
{
	while(scanf("%s", s1[0]) != EOF) {
		for(len1 = 1; ; ++len1) {
			scanf("%s", s1[len1]);
			if(strcmp(s1[len1], "#") == 0) break;
		}
		for(len2 = 0; ; ++len2) {
			scanf("%s", s2[len2]);
			if(strcmp(s2[len2], "#") == 0) break;
		}
		lcs();
		print(len1, len2);
		printf("\n");
	}
	return 0;
}

本文链接：https://blog.csdn.net/GKHack/article/details/49148257

原作者删帖不实内容删帖广告或垃圾文章投诉

智能推荐

达美乐披萨微信小程序抓包发包快速领取奖励_windowswechat(0x63090a13)-程序员宅基地

文章浏览阅读109次。通过发包帮助快速领取达美乐抽奖奖励，早日抽到免费披萨。_windowswechat(0x63090a13)

分享三种计算机专业毕业设计模板附下载地址_计算机系统毕业设计模板-程序员宅基地

文章浏览阅读599次。一、web管理类计算机专业毕业设计模板网络的快速发展，系统管理工作也显得尤为重要，信息管理随着科学化的发展达到了存储量大，速度快，完善等特点，管理工作得到发展并促进信息管理，信息化统一管理被更多的用户所接受。互联网技术的提升给人们的生活带来日新月异的变化，信息化潮流使得更多的人们选择上网来充实自我以及实现其他更便捷的服务。时代的进步，各种智能化管理也越来越普及，随着校园生活的不断丰富，校园内各项事务也在不断增加，因此，要开发一个可以高效率，低成本的高校师生信息管理系统，不仅便于校园管理员的统一管理，还可以_计算机系统毕业设计模板

java毕业设计城市出行行程智能推荐系统Mybatis+系统+数据库+调试部署-程序员宅基地

文章浏览阅读81次。?java毕业设计城市出行行程智能推荐系统Mybatis+系统+数据库+调试部署。前端技术：Layui、HTML、CSS、JS、JQuery等技术。springboot基于SpringBoot的桦木加工厂管理系统。springboot基于web的数码产品应用平台设计与实现。ssm基于Java的幼儿早教系统软件的设计与实现。springboot多维分类的知识管理系统。springboot学生网上请假系统。

关于Android 11检测当前是否处于耳机或者蓝牙状态_android 判断当前是否连接耳机-程序员宅基地

文章浏览阅读875次，点赞14次，收藏20次。关于Android 11 设备对当前耳机状态以及蓝牙A2DP状态的判别_android 判断当前是否连接耳机

linux双括号用法,linux shell (()) 双括号运算符使用-程序员宅基地

文章浏览阅读359次。估计很多朋友都感觉比较难以接受。特变逻辑运算符”[]”使用时候，必须保证运算符与算数之间有空格。四则运算也只能借助：let,expr等命令完成。今天讲的双括号”(())”结构语句，就是对shell中算数及赋值运算的扩展。使用方法：语法：((表达式1,表达式2…))特点：1、在双括号结构中，所有表达式可以像c语言一样，如：a++,b--等。2、在双括号结构中，所有变量可以不加入：“$”符号前缀...

HbuilderX正式版在pages.json中不提示图片路径_hbuilder路径没提示-程序员宅基地

文章浏览阅读677次，点赞8次，收藏9次。HbuilderX正式版在pages.json中不提示图片路径_hbuilder路径没提示