首页 > 代码库 > UVa 531 - Compromise

UVa 531 - Compromise

题目:给你两个文章,求里面最多的按顺序出现的单词。

分析:dp,LCS(最大公共子序列)。直接求最大公共子序列,每个单词当做一个元素即可;

            注意记录路径:如果匹配成功记录前驱,否则取前面取得的最大值的前驱(这里合成一个数字);

            设状态f(i,j)为串S【0..i-1】与串T【0..j-1】的最大公共子序列。

            有状态转移方程: f(i,j)= f(i-1,j-1)                                  {S【i-1】与T【j-1】相同}

                                            f(i,j)= max(f(i-1,j),f(i,j-1)) {S【i-1】与T【j-1】不同}

说明:注意输出时的格式,多打个空格WA了好几次才发现。

#include <iostream>
#include <cstdlib>
#include <cstring>
#include <cstdio>

using namespace std;

char word1[104][32];
char word2[104][32];
int  F[104][104],dp[104][104];

void output( int id, int flag )
{
	if ( id/1000 && id%1000 ) {
		output( F[id/1000-1][id%1000-1], 1 );
		printf("%s",word1[id/1000-1]);
		if ( flag ) printf(" ");
	}
}

int main()
{
	while ( cin >> word1[0] ) {
		int count1 = 1,count2 = 0;
		if ( strcmp(word1[0], "#") ) {
			while ( cin >> word1[count1] && strcmp( word1[count1], "#" ) )
				count1 ++;
		}else count1 = 0;
		
		while ( cin >> word2[count2] && strcmp( word2[count2], "#" ) )
			count2 ++;
		
		for ( int i = 0 ; i < 102 ; ++ i )
		for ( int j = 0 ; j < 102 ; ++ j ) {
			F[i][j] = 0; dp[i][j] = 0;
		}
		
		for ( int i = 1 ; i <= count1 ; ++ i )
		for ( int j = 1 ; j <= count2 ; ++ j )
			if ( !strcmp( word1[i-1], word2[j-1] ) ) {
				dp[i][j] = dp[i-1][j-1]+1;
				F[i][j] = 1000*i+j;
            }else if ( dp[i-1][j] < dp[i][j-1] ) {   
                dp[i][j] = dp[i][j-1];  
                F[i][j] = F[i][j-1];  
            }else {
				dp[i][j] = dp[i-1][j];  
                F[i][j] = F[i-1][j];
            }
		
		if ( F[count1][count2] )
			output( F[count1][count2], 0 );
		printf("\n");
	}
	return 0;
}