poj 1934 DP

参照别人的思路：点击打开链接

它的思路是：

1）首先按照常规的方法求出最长公共子序列的长度

也就是用O(MN)的那个动态规划，结果放在二维数组dp里

dp[i][j] = { 字串a的1~i部分与字串b的1~j部分的最长公共子序列的长度 }

2）求辅助数组

last1[i][j] = { 到下标i为止，字符j在字串a中最后一次出现的下标 }

last2[i][j] = { 到下标i为止，字符j在字串b中最后一次出现的下标 }

3）枚举最长公共字串的每一个字符

从最后一个字符开始枚举

比如说现在枚举最后一个字符是'C'的情况。

那么 'CDCD' 与 'FUCKC' 这两个字串。

一共有 (0, 2) (0, 4)  (2, 2)  (2. 4) 这四种可能。

很明显前三个是可以舍弃的，因为第四个优于前三个，为后续的枚举提供了更大的空间。

last数组正好是用来做这个的。

4）排序输出

代码里用了stl的set。

注意，由于刚刚的枚举过程是针对每个字符，所以是不用判重的。

AC代码如下：

#include <iostream>
#include <cstdio>
#include <cstring>
#include <string>
#include <set>
#include <algorithm>
using namespace std;

char a[100], b[100];
int lcm, tot;
int dp[100][100];
int last1[100][27], last2[100][27];
char ans_temp[100];
set<string> ans;
int lengtha, lengthb;

void calc_lcm(){
	memset( dp, 0, sizeof( dp ) );

	for( int i = 1; i <= lengtha; i++ ){
		for( int j = 1; j <= lengthb; j++ ){
			if( a[i] == b[j] ){
				dp[i][j] = max( dp[i][j], dp[i-1][j-1] + 1 );
			}else{
				dp[i][j] = max( dp[i][j], max( dp[i-1][j], dp[i][j-1] ) );
			}
		}
	}

	lcm = dp[lengtha][lengthb];
}

void find_ans( int pos_a, int pos_b, int length ){
	if( length <= 0 ){
		ans.insert( ans_temp + 1 );
	}
	if( pos_a > 0 && pos_b > 0 ){
		for( int i = 25; i >= 0; i-- ){
			int temp1 = last1[pos_a][i];
			int temp2 = last2[pos_b][i];
			if( dp[temp1][temp2] == length ){
				ans_temp[length] = 'a' + i;
				find_ans( temp1 - 1, temp2 - 1, length - 1 );
			}
		}
	}
}

void solve(){
	memset( last1, 0, sizeof( last1 ) );
	memset( last2, 0, sizeof( last2 ) );

	for( int i = 1; i <= lengtha; i++ ){
		for( int j = 0; j < 26; j++ ){
			if( a[i] == ( 'a' + j ) ){
				last1[i][j] = i;
			}else{
				last1[i][j] = last1[i-1][j];
			}
		}
	}
	for( int i = 1; i <= lengthb; i++ ){
		for( int j = 0; j < 26; j++ ){
			if( b[i] == ( 'a' + j ) ){
				last2[i][j] = i;
			}else{
				last2[i][j] = last2[i-1][j];
			}
		}
	}

	ans_temp[lcm+1] = 0;
	find_ans( lengtha, lengthb, lcm );

	set<string>::iterator it = ans.begin();
	while( it != ans.end() ){
		cout << *it++ << endl;
	}
}

int main(){
	while( scanf( "%s%s", a + 1, b + 1 ) != EOF ){
		lengtha = strlen( a + 1 );
		lengthb = strlen( b + 1 );
		calc_lcm();

		solve();
	}
	return 0;
}