[UVa] 10066 - The Twin Towers

題目網址:  http://goo.gl/mL97hN

題 意: 有兩座由圓柱堆疊而成的塔，圓柱的高皆一樣，但半徑不同，所以兩座塔的樣子也不同，想從兩座塔各拿走某些圓柱，使得兩座塔等高且樣子相同，問最後兩座塔的高度。


解法: 很明顯就是求兩序列的LCS(longest common subsequence) 喔。

TAG:DP, lcs

注意:

程式碼:

	/**
	* Tittle: 10066 - The Twin Towers
	* Author: Cheng-Shih, Wong
	* Date: 2015/03/15
	* File: 10066 - The Twin Towers.cpp - solve it
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	using namespace std;
	// definitions
	#define FOR(i,a,b) for( int i=(a),_n=(b); i<=_n; ++i )
	#define clr(x,v) memset( x, v, sizeof(x) )
	#define N 105
	// declarations
	int ti = 1;
	int n1, n2;
	int a[N], b[N];
	int dp[N][N];
	// functions
	// main function
	int main( void )
	{
	// input
	while( scanf( "%d%d", &n1, &n2 )==2 && (n1||n2) ) {
	FOR( i, 1, n1 ) scanf( "%d", &a[i] );
	FOR( i, 1, n2 ) scanf( "%d", &b[i] );
	// init
	clr( dp, 0 );
	// solve
	FOR( i, 1, n1 ) FOR( j, 1, n2 ) {
	if( a[i] == b[j] ) dp[i][j] = dp[i-1][j-1]+1;
	else dp[i][j] = max( dp[i][j-1], dp[i-1][j] );
	}
	// output
	printf( "Twin Towers #%d\n", ti++ );
	printf( "Number of Tiles : %d\n\n", dp[n1][n2] );
	}
	return 0;
	}

view raw 10066 - The Twin Towers.cpp hosted with ❤ by GitHub