[UVa] 10081 - Tight Words

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

題 意: 給定兩個整數 k, n，如果一個由 0 ~ k 組成長度為 n 的字串是 "tight"，則代表相鄰的兩位數差不超過 1，問所有字串中包含 "tight" 字串的比例。


解法: 用DP解，當求第 i 層的答案時，會跟第 i-1 層的答案相關。

dp[ i ][ j ] =
{ 1/(k+1),if i = 0 and 0 <= j <= k
{ 1/(k+1) * ( dp[i-1][j] + dp[i-1][j+1] ), if i > 0 and j = 0
{ 1/(k+1) * ( dp[i-1][j-1] + dp[i-1][j] + dp[i-1][j+1] ), if i > 0 and 1 <= j <= k-1
{ 1/(k+1) * ( dp[i-1][j-1] + dp[i-1][j] ), if i > 0 and j = k
代表當長度為 i+1 且結尾為 j 的字串出現的機率

TAG:DP

注意:可以利用滾動數組來降低空間複雜度

程式碼:

	/**
	* Tittle: 10081 - Tight Words
	* Author: Cheng-Shih, Wong
	* Date: 2015/03/18
	*/
	// 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 cur(x) ((x)&1)
	#define pre(x) (((x)-1)&1)
	// declarations
	double dp[2][10];
	// functions
	int k, n;
	double ans;
	// main function
	int main( void )
	{
	double d;
	// input
	while( scanf( "%d%d", &k, &n )==2 ) {
	// solve
	clr( dp, 0 );
	d = k+1.0;
	FOR( i, 0, k ) dp[0][i] = 1/d;
	FOR( i, 1, n-1 ) {
	clr( dp[cur(i)], 0 );
	FOR( j, 0, k ) {
	if( j > 0 ) dp[cur(i)][j] += dp[pre(i)][j-1];
	dp[cur(i)][j] += dp[pre(i)][j];
	if( j < k ) dp[cur(i)][j] += dp[pre(i)][j+1];
	dp[cur(i)][j] *= 1/d;
	}
	}
	ans = 0;
	FOR( i, 0, k ) ans += dp[cur(n-1)][i];
	// output
	printf( "%.5lf\n", ans*100 );
	}
	return 0;
	}

view raw 10081 - Tight Words.cpp hosted with ❤ by GitHub