[UVa] 10328 - Coin Toss

題目網址: https://goo.gl/MxsVIi

題意:
(from luckycat)


解法:
因為最多有 2^100 種結果，所以看起來就很 DP。
我們考慮第 n 次的丟擲結果 (H、T) 且將它放到前 n-1 次結果的前面。
所以定義 dp[ n ][ k ][ pre ] 為當丟擲了 n 次且其中最長的連續 H 長度為 k 且結果串從最前面算起來最長連續 H 的長度。舉個例子： HHTHHHT 此結果串就屬於 dp[ 7 ][ 3 ][ 2 ] 裡面！
遞迴式：

dp[ n ][ k ][ pre ] = 
{ 1, if k = pre = 0
{ dp[ n-1 ][ k-1 ][ pre-1 ]+dp[ n-1 ][ k ][ pre-1 ], if k and pre > 0
{ sum( dp[ n-1 ][ k ][ u ], 0 <= u <= k ), if k > 0 and pre = 0

TAG: DP, BigNum

注意: 因為答案會到 2^100-1，所以要用大數喔！

程式碼:

	/**
	* Tittle: 10328 - Coin Toss
	* Author: Cheng-Shih, Wong
	* Date: 2015/06/27
	*/
	import java.util.*;
	import java.math.*;
	public class Main {
	static Scanner input = new Scanner(System.in);
	static int N = 105;
	static BigInteger[][][] dp = new BigInteger[N][N][N];
	static BigInteger[][] ans = new BigInteger[N][N];
	static int n, k;
	public static void main( String[] args ) {
	init();
	while( input.hasNext() ) {
	n = input.nextInt();
	k = input.nextInt();
	System.out.println(ans[n][k].toString());
	}
	input.close();
	}
	private static void init() {
	Queue<State> que = new LinkedList<State>();
	boolean[][][] inQ = new boolean[N][N][N];
	State stt;
	int num, max, pre;
	int nxtNum, nxtMax, nxtPre;
	for( int i=0; i<N; ++i )
	for( int j=0; j<N; ++j )
	for( int k=0; k<N; ++k )
	dp[i][j][k] = BigInteger.ZERO;
	for( boolean[][] i : inQ )
	for( boolean[] j : i )
	for( boolean k : j )
	k = false;
	dp[0][0][0] = BigInteger.ONE;
	que.offer( new State(0,0,0) );
	inQ[0][0][0] = true;
	while( que.peek() != null ) {
	stt = que.poll();
	num = stt.num;
	max = stt.max;
	pre = stt.pre;
	if( num >= 100 ) continue;
	nxtNum = num+1;
	nxtPre = pre+1;
	if( nxtPre > max )
	nxtMax = nxtPre;
	else
	nxtMax = max;
	dp[nxtNum][nxtMax][nxtPre] = dp[nxtNum][nxtMax][nxtPre].add(
	dp[num][max][pre] );
	if( !inQ[nxtNum][nxtMax][nxtPre] ) {
	que.offer( new State(nxtNum,nxtMax,nxtPre) );
	inQ[nxtNum][nxtMax][nxtPre] = true;
	}
	nxtPre = 0;
	nxtMax = max;
	dp[nxtNum][nxtMax][nxtPre] = dp[nxtNum][nxtMax][nxtPre].add(
	dp[num][max][pre] );
	if( !inQ[nxtNum][nxtMax][nxtPre] ) {
	que.offer( new State(nxtNum,nxtMax,nxtPre) );
	inQ[nxtNum][nxtMax][nxtPre] = true;
	}
	}
	for( int i=0; i<N; ++i ) for( int j=0; j<N; ++j )
	ans[i][j] = BigInteger.ZERO;
	for( int i=1; i<=100; ++i ) {
	for( int j=100; j>=1; --j ) {
	ans[i][j] = ans[i][j].add( ans[i][j+1] );
	for( int k=0; k<=j; ++k )
	ans[i][j] = ans[i][j].add( dp[i][j][k] );
	}
	}
	}
	static class State {
	public int num, max, pre;
	public State( int _n, int _m, int _p ) {
	num = _n;
	max = _m;
	pre = _p;
	}
	}
	}

view raw 10328 - Coin Toss.java hosted with ❤ by GitHub