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;
}