PKU 2411-Mondriaan's Dream
問題概要
WxHのマスに1x2のタイルを敷き詰める場合の数を求めよ
解法
2^w個のデーターを保持しつつメモ化再帰
実装(Java)
import java.util.*; import java.math.*; import java.io.*; import java.util.regex.*; import static java.lang.Math.*; import static java.util.Arrays.*; import static java.lang.System.*; public class Main { Scanner input; long [][][]dp; int W,H,MASK; long dfs(int bit,int x,int y){ if(x==W)return dfs(bit,0,y+1); if(y==H&&bit==0)return 1; if(y==H)return 0; if(dp[x][y][bit]>=0)return dp[x][y][bit]; long res=0; if((bit&1)==1){//既に何かおかれている res+=dfs((bit>>1),x+1,y); }else{ //横における if(x<W-1&&((bit>>1)&1)==0){ res+=dfs((bit>>2),x+2,y); } //縦には絶対における res+=dfs((bit>>1)|(1<<(W-1)),x+1,y); } return dp[x][y][bit]=res; } long solve(int W_,int H_){ W=W_;H=H_; MASK=(1<<W)-1; if(W*H%2==1)return 0; dp=new long[11][11][1<<11]; for(int y=0;y<H;y++){ for(int x=0;x<W;x++){ for(int k=0;k<1<<W;k++){ dp[x][y][k]=-1; } } } return dfs(0,0,0); } void run(){ input=new Scanner(System.in); int W,H; while(true){ W=input.nextInt();H=input.nextInt(); if(W==0)break; printf("%d\n",solve(W,H)); } } void printf(String format,Object... args){ System.out.printf(format, args); } public static void main(String[] args) { new Main().run(); } }