当前位置:首页 » Project Euler » 详细页

Counting block combinations I 题号:114 难度: 35 中英对照

A row measuring seven units in length has red blocks with a minimum length of three units placed on it, such that any two red blocks (which are allowed to be different lengths) are separated by at least one black square. There are exactly seventeen ways of doing this.

 

How many ways can a row measuring fifty units in length be filled?

NOTE: Although the example above does not lend itself to the possibility, in general it is permitted to mix block sizes. For example, on a row measuring eight units in length you could use red (3), black (1), and red (4).


Solution

动态规划。 考虑$dp[i][j]$,表示长度为$i$时,左侧为黑色($j=0$)或者红色($j=1$)时的答案。 初始条件为:$i< 3$,$dp[i][0]=1,dp[i][1]=0$。对于$dp[3][0]=dp[3][1]=1$。 递推为: 1. 计算$dp[i][0]$,则左侧为黑色,可以放一个黑色块,右侧$i-1$的空间随便填,即为$dp[i-1][0]+dp[i-1][1]$。 2. 计算$dp[i][1]$,则左侧为红色,可以考虑枚举左侧红色块的长度为$j$,那么剩下部分需要填入左侧为黑色的$dp[i-j][0]$。

Code


public final class p114 {
    public static void main(String[] args) {
        long start=System.nanoTime();
        String result = run();        
        long end=System.nanoTime();
        System.out.println(result);
        System.out.println( (end-start)/1000000 + "ms" );
    }
    
    static public long dp[][]=new long[55][2];
    static public String run(){
    	for(int i=0;i<=2;i++){
    		dp[i][0]=1;
    		dp[i][1]=0;
    	}
    	dp[3][0]=1;//black
    	dp[3][1]=1;//red
    	int ans=50;
    	for(int i=4;i<=ans;i++){
    		dp[i][0]=dp[i-1][0]+dp[i-1][1];
    		dp[i][1]=0;
    		for(int j=3;j<=i;j++)
    			dp[i][1]+=dp[i-j][0];
    	}
    	return Long.toString(dp[ans][0]+dp[ans][1]);
    }
    
}
16475640049
0ms