[UVa] 10128 - Queue

題目網址: http://goo.gl/7TD7JM

題意: 有 n 個身高皆不同的人排成一排，問左邊看到 p 個人，右邊能看到 r 個人，問有幾種排列可能。


解法: 要找排列情況可聯想 DP，所以想辦法想出遞迴方程，想像當總人數為 n' 個人，左邊看的到 p' 個人，右邊看的到 r' 個人，想把最矮的人拿掉的所有情況，假設最矮的人站在第一個位子，那拿掉他之後從左邊看就會少一個人，如果最矮的人站在最後一個位子，拿掉他後從右邊看也會少一個，如果最矮的人站在中間任何一個位子，拿掉他之後，從左邊或右邊看人數不變。

dp[n'][p'][r'] =
{ 1, if n' = p' = r' = 1
{ dp[n'-1][p'-1][r'] + dp[n'-1][p'][r'] + dp[n'-1][p'][r'-1], if n' > 1, 1 <= p', r' <= n'

TAG: DP

注意:

程式碼:

	/**
	* Tittle: 10128 - Queue
	* Author: Cheng-Shih, Wong
	* Date: 2015/04/04
	*/
	// 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 15
	// declarations
	int t;
	int n, p, r;
	int dp[N][N][N];
	// functions
	// main function
	int main( void )
	{
	// solve
	clr( dp, 0 );
	dp[1][1][1] = 1;
	FOR( i, 1, 12 ) FOR( j, 1, i ) FOR( k, 1, i ) if( dp[i][j][k] ) {
	dp[i+1][j+1][k] += dp[i][j][k];
	dp[i+1][j][k+1] += dp[i][j][k];
	dp[i+1][j][k] += (i-1)*dp[i][j][k];
	}
	// input
	scanf( "%d", &t );
	while( t-- ) {
	scanf( "%d%d%d", &n, &p, &r );
	// output
	printf( "%d\n", dp[n][p][r] );
	}
	return 0;
	}

view raw 10128 - Queue.cpp hosted with ❤ by GitHub