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

Red, green or blue tiles 题号:116 难度: 30 中英对照

A row of five black square tiles is to have a number of its tiles replaced with coloured oblong tiles chosen from red (length two), green (length three), or blue (length four).

If red tiles are chosen there are exactly seven ways this can be done.

 

If green tiles are chosen there are three ways.

 

And if blue tiles are chosen there are two ways.

Assuming that colours cannot be mixed there are 7 + 3 + 2 = 12 ways of replacing the black tiles in a row measuring five units in length.

How many different ways can the black tiles in a row measuring fifty units in length be replaced if colours cannot be mixed and at least one coloured tile must be used?

NOTE: This is related to Problem 117.


Solution

动态规划。 因为颜色不能混用,所以对每一种颜色分别dp。 用$dp[i]$表示长度为$i$的块组成一行的方案数,则该dp对答案的贡献为$dp[50]-1$。 初始条件为$dp[0]=1$。 递推为$dp[i]=dp[i-1]+(i>=X?dp[i-X]:0)$,其中$X$为对应颜色的砖块长度,即为$2,3,4$。

Code


public final class p115 {
    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 String run(){
    	long ans=0;
    	final int N=50;
		for(int j=2;j<=4;j++){
			long[] dp=new long[N+1];
			dp[0]=1;
			for(int i=1;i<=N;i++){
				dp[i]=dp[i-1];
				if(i>=j)
					dp[i]+=dp[i-j];
    		}
			ans+=dp[N]-1;
    	}
    	return Long.toString(ans);
    }
    
}
20492570929
0ms