当前位置:首页(Home) >> 新闻资源(News List)

时间:2015-06-11 来源:

hdu1143TriTiling 【编程语言】

如果长度L是2,那么有3种拼法,所以是3*f[n-2] 如果长度L是4或以上,有2种拼法,所以是2*f[n-L] (L 从4到n) 前面我们最初拼的时候只取了对称的两种情况之一,因此,如果x>2, 拼出一个不能被竖线切割的矩形的方法只有两种。 那么递推公式自然就有了,f(n)=3*f(n-2)+2*f(n-4)+…+2*f(0),

然后再写出f(n-2)的递推式后两式作差就可以得到f(n)=4*f(n-2)-f(n-4),

递归的边界是f(0)=1,f(2)=4。

Tri Tiling 三瓷砖 Time Limit: 2000/1000 MS (Java/Others)    Memory Limit: 65536/32768 K (Java/Others) Total Submission(s): 2676    Accepted Submission(s): 1511 Problem Description In how many ways can you tile a 3xn rectangle with 2x1 dominoes? Here is a sample tiling of a 3x12 rectangle. 用2 x1的多米诺骨牌铺在3 x n 的矩形瓷砖中,能铺多少种?下面是一个示例3 x12矩形的瓷砖。   Input Input consists of several test cases followed by a line containing -1. Each test case is a line containing an integer 0 ≤ n ≤ 30.  输入包含多个测试用例,-1表示输入结束。每个测试用例的第一行包含一个整数0≤n≤30,表示测试用例的个数。 Output For each test case, output one integer number giving the number of possible tilings.  在单独的一行输出所有可能的总数目。 Sample Input 2 8 12 -1   Sample Output 3 153 2131  

import java.util.Scanner; public class Main { public static void main(String[] args) { Scanner sc = new Scanner(System.in); int[] mat = new int[31]; mat[0] = 1;//初始为1*** mat[2] = 3; for (int i = 4; i < mat.length; i+=2) { mat[i] = mat[i-2]*4 - mat[i-4]; } while (sc.hasNext()) { int n = sc.nextInt(); if (n == -1) { return; } if ((n & 0x01) == 0) {// 偶数 System.out.println(mat[n]); }else{ System.out.println(0); } } } }

点击次数:1609
作者: