UVa 10328 : Coin Toss

UVa演習 2014/7/14 (月) 問３

問題リンク : http://uva.onlinejudge.org/external/103/10328.html

問題概要：
n回コインをなげたとき、2^nだけコインの状態がある
そのうち連続でk回以上表がでているようなものはいくつあるか？

解法:
動的計画法
dp[何桁までみたか][これまでみた中で最大何回連続して表がでたか][最後のコインの結果からみて連続して何回表がでているか] := そのときの数
BigIntegerを使わないといけないくらい答えが大きくなるので注意

コード:

import java.io.*;
import java.math.*;
import java.util.*;

class Main{

    public static void main(String args[]){
        Scanner in = new Scanner(System.in);
        BigInteger[][][] dp = new BigInteger[110][110][110];
        int N = 100,K;
        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;
        dp[0][0][0] = BigInteger.ONE;
        for(int i=0;i<N;i++){ // 今みている桁
            for(int j=0;j<=i;j++){ // i個の文字列中にある最長のHの列の長さ
                for(int k=0;k<=j;k++){ // 文字列の最後から何個Hが連続しているか
                    if( dp[i][j][k].compareTo(BigInteger.ZERO) == 0 ) continue;
                    dp[i+1][Math.max(j,k+1)][k+1] = dp[i+1][Math.max(j,k+1)][k+1].add(dp[i][j][k]);
                    dp[i+1][j][0] = dp[i+1][j][0].add(dp[i][j][k]);
                }
            }
        }

        while( in.hasNext() ){
            N = in.nextInt();
            K = in.nextInt();
            BigInteger sum = BigInteger.ZERO;
            for(int i=K;i<=N;i++) for(int j=0;j<=N;j++) sum = sum.add(dp[N][i][j]);
            System.out.println(sum);
        }
    }

}