POJ——2250 Compromise

红太狼 2022-08-11 04:58 80阅读 0赞

就是最长公共子序列

#include <cstdio>
    #include <cstring>
    #include <iostream>
    using namespace std;
    // const int N=3500;
    char str1[105][35],str2[105][35];
    int main()
    {
    	//freopen("text.txt","r",stdin);
    	while(scanf("%s",str1[0])!=EOF&&str1[0][0]!='#')
    	{
    	int len1=1;
    	while(scanf("%s",str1[len1])==1&&str1[len1][0]!='#')
    	len1++;
    	int len2=0;
    	while(scanf("%s",str2[len2])==1&&str2[len2][0]!='#')
    	len2++;
    	int c[105][105];
    	for(int i=1;i<=len1;i++)c[i][len2]=0;
    	for(int i=1;i<=len2;i++)c[len1][i]=0;
    	int i,j;	
    	for(i=len1-1;i>=0;i--)
    		for(j=len2-1;j>=0;j--)
    			if(strcmp(str1[i],str2[j])==0)
    				{
    					c[i][j]=c[i+1][j+1]+1;s[i][j]=1;
    				}
    			else 
    			{
    				s[i][j]=0;
    				if(c[i][j+1]>c[i+1][j])c[i][j]=c[i][j+1];
    				else c[i][j]=c[i+1][j];
    			}
    		int t=0,w=0;
    		for(i=0;i<len1;i++)
    			for(j=0;j<len2;j++)
    				if(s[i][j]==1&&c[i][j]==c[0][0]-w)
    				{
    					printf("%s ",str1[i]);
    					w++;t=j+1;break;
    				}
    				putchar(10);
    	}
    	return 0;
    }

发表评论取消回复

表情：

评论列表（有 0 条评论，80人围观）

还没有评论，来说两句吧...

相关阅读

相关 poj 1064 java_poj1064

Cable master Time Limit: 1000MS Memory Limit: 10000K Total Submissions: 15127 Accept

r囧r小猫/ 2022年11月05日 03:30/ 0 赞/ 133 阅读

相关【POJ】：POJ 3984

题目链接：[http://poj.org/problem?id=3984][http_poj.org_problem_id_3984] 题目解析：这题算是搜索里面的简单题了吧

Myth丶恋晨/ 2022年08月23日 04:50/ 0 赞/ 172 阅读

相关 POJ——2250 Compromise

就是最长公共子序列 include <cstdio> include <cstring> include <iostream> using n

红太狼/ 2022年08月11日 04:58/ 0 赞/ 81 阅读

相关 poj-2250Compromise（LCS+标记数组）

Compromise <table> <tbody> <tr> <td><strong>Time Limit:</strong> 1000MS</

╰半夏微凉°/ 2022年08月10日 05:47/ 0 赞/ 56 阅读

相关 Poj1129

当一个广播电台在一个非常大的地区，广播站会用中继器来转播信号以使得每一个接收器都能接收到一个强烈的信号。然而，每个中继器必须慎重选择使用，使相邻的中继器不互相干扰。如果相邻的中

小鱼儿/ 2022年08月05日 08:52/ 0 赞/ 149 阅读

相关 pku 1015 Jury Compromise DP

\include <iostream> \include <cstdio> \include <cstring> \include <exception> using name

小咪咪/ 2022年07月12日 10:15/ 0 赞/ 107 阅读

相关 poj1321+poj2251

poj1321代码实现（dfs）： include <iostream> include <string.h> using namespace std

心已赠人/ 2022年05月30日 04:08/ 0 赞/ 156 阅读

相关 Compromise————LCS+输出路径

In a few months the European Currency Union will become a reality. However, to join the

﹏ヽ暗。殇╰゛Y/ 2022年05月17日 10:08/ 0 赞/ 110 阅读

相关 Jury Compromise

[Jury Compromise][] 有n对数，每对数由\\((d\_i,p\_i)\\)组成，现在要求选出m对数，\\(\\sum\\)表示对这m对数中的元素累加,在\\

心已赠人/ 2022年01月08日 00:25/ 0 赞/ 162 阅读

相关 POJ1015 Jury Compromise

题意：《算法竞赛进阶指南》P278。分析：《算法竞赛进阶指南》P278-279。代码： include <iostream> includ

柔光的暖阳◎/ 2021年11月27日 05:14/ 0 赞/ 128 阅读