[UVa] 10131 - Is Bigger Smarter?

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

題意: 有一群大象，給每隻大象的體重 W 與智商 S，要你找出最大的子集合，滿足子集合 { a1, a2, a3, ..., an }中每隻大象滿足 W[ai] < W[ai+1] 且 S[ai] > S[ai+1]。


解法: LIS的變形，先將大象以體重排序，接著用LIS的方法再稍改即可。

(為求方便，加入第 0 隻大象，此大象體重最小，智商最大)
遞迴式: dp[i] 代表以第 i 隻大象為尾的最長大象序列的長度
dp[i] = 
{ 0, if i = 0
{ max{ dp[j] }+1, if W[j] < W[i] & S[j] > S[i] & 0 <= j < i

TAG: DP, LIS

注意:

程式碼:

	/**
	* Tittle: 10131 - Is Bigger Smarter?
	* Author: Cheng-Shih, Wong
	* Date: 2015/04/08
	*/
	// include files
	#include <iostream>
	#include <cstdio>
	#include <cstring>
	#include <algorithm>
	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 1005
	class Elephant {
	public:
	int w, s;
	int id;
	Elephant( int _w=0, int _s=0 ): w(_w), s(_s) {}
	const bool operator<( const Elephant &op ) const {
	return (w < op.w);
	}
	};
	// declarations
	int n;
	Elephant ep[N];
	int ans, ansi;
	int dp[N], pre[N];
	// functions
	void output( int u )
	{
	if( pre[u] )
	output( pre[u] );
	printf( "%d\n", ep[u].id );
	}
	bool check( int a, int b )
	{
	return (ep[a].w<ep[b].w && ep[a].s > ep[b].s);
	}
	// main function
	int main( void )
	{
	// input
	n = 1;
	while( scanf( "%d%d", &ep[n].w, &ep[n].s )==2 ) {
	ep[n].id = n;
	++n;
	}
	// solve
	ans = 0;
	ep[0].w = 0;
	ep[0].s = 10001;
	sort( ep+1, ep+1+n );
	clr( dp, 0 );
	clr( pre, 0 );
	FOR( i, 1, n ) {
	for( int j=i-1; j>=0; --j ) if( check(j,i) && dp[i]<dp[j]+1 ) {
	dp[i] = dp[j]+1;
	pre[i] = j;
	}
	if( dp[i] > ans ) {
	ans = dp[i];
	ansi = i;
	}
	}
	// output
	printf( "%d\n", ans );
	output( ansi );
	return 0;
	}

view raw 10131 - Is Bigger Smarter?.cpp hosted with ❤ by GitHub