首页 > 专题系列 > Java解POJ > POJ 2506 Tiling [解题报告] Java
2013
11-11

POJ 2506 Tiling [解题报告] Java

Tiling

问题描述 :

In how many ways can you tile a 2xn rectangle by 2×1 or 2×2 tiles?

Here is a sample tiling of a 2×17 rectangle.

输入:

Input is a sequence of lines, each line containing an integer number 0 <= n <= 250.

输出:

For each line of input, output one integer number in a separate line giving the number of possible tilings of a 2xn rectangle.

样例输入:

2
8
12
100
200

样例输出:

3
171
2731
845100400152152934331135470251
1071292029505993517027974728227441735014801995855195223534251

解题代码:

import java.util.*;
import java.math.*;
public class Main{
 static BigInteger[] ans;
 public static void main(String args[])
  {
   Scanner sc=new Scanner(System.in);
   ans=new BigInteger[251];
   ans[0]=BigInteger.valueOf(1);
   ans[1]=BigInteger.valueOf(1);
   ans[2]=BigInteger.valueOf(3);
   for(int i=3;i<=250;i++)
    ans[i]=ans[i-1].add(ans[i-2].multiply(BigInteger.valueOf(2)));
   while(sc.hasNextInt()){
    int n=sc.nextInt();
    System.out.println(ans[n]);
   }
  }
}

  1. #include <cstdio>
    #include <algorithm>

    struct LWPair{
    int l,w;
    };

    int main() {
    //freopen("input.txt","r",stdin);
    const int MAXSIZE=5000, MAXVAL=10000;
    LWPair sticks[MAXSIZE];
    int store[MAXSIZE];
    int ncase, nstick, length,width, tmp, time, i,j;
    if(scanf("%d",&ncase)!=1) return -1;
    while(ncase– && scanf("%d",&nstick)==1) {
    for(i=0;i<nstick;++i) scanf("%d%d",&sticks .l,&sticks .w);
    std::sort(sticks,sticks+nstick,[](const LWPair &lhs, const LWPair &rhs) { return lhs.l>rhs.l || lhs.l==rhs.l && lhs.w>rhs.w; });
    for(time=-1,i=0;i<nstick;++i) {
    tmp=sticks .w;
    for(j=time;j>=0 && store >=tmp;–j) ; // search from right to left
    if(j==time) { store[++time]=tmp; }
    else { store[j+1]=tmp; }
    }
    printf("%dn",time+1);
    }
    return 0;
    }