TIOJ 1452 巧拼放置問題

poao899    460K    228MS    G++     0.77K     2009-10-19 22:28:45                                  .

耶總算過了XD


O( n*4^m)超噁心複雜度orz

總狀態數O(n*2^m) 狀態轉移O(2^m)

不知道當時考出來puts("0")騙分可以騙幾筆XD



耶今天練習賽被電爆不開心XD

//***********************************

#include<stdio.h>
long long way[13][8192];int n,m;
long long dp(int stat,int nstat,int nown,int nowm){
    if(nown>=n)return stat==0;
    if(nowm==0 && way[nown][stat])return way[nown][stat];
    if(nowm>=m)return dp(nstat,0,nown+1,0);
    long long ways=0;
    if((stat & (1<<nowm)) ==0){
        ways+=dp(stat|(1<<nowm) , nstat|(1<<nowm) , nown , nowm+1);
        if(nowm<m-1 && (stat & (1<<nowm+1)) ==0){
            ways+=dp(stat|(1<<nowm+1)|(1<<nowm) , nstat , nown , nowm+2);
        }
    }
    else{
        ways+=dp(stat,nstat,nown,nowm+1);
    }
    if(nowm==0)way[nown][stat]=ways;
    return ways;
}
main(){
    while(scanf("%d%d",&n,&m),n+m){
        for(int i=0;i<12;i++)
            for(int j=0;j<4096;j++)
                way[i][j]=0;
        if(n%2 && m%2){puts("0");continue;}
        if(n<m){int t=m;m=n;n=t;}
        printf("%I64d\n",dp(0,0,0,0));
    }
}