程序師世界是廣大編程愛好者互助、分享、學習的平台,程序師世界有你更精彩!
首頁
編程語言
C語言|JAVA編程
Python編程
網頁編程
ASP編程|PHP編程
JSP編程
數據庫知識
MYSQL數據庫|SqlServer數據庫
Oracle數據庫|DB2數據庫
 程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> poj2411 2663 2420 dp+狀態壓縮(多米諾骨牌問題)

poj2411 2663 2420 dp+狀態壓縮(多米諾骨牌問題)

編輯:C++入門知識

題目描述:用1*2 的矩形通過組合拼成大矩形,求拼成指定的大矩形有幾種拼法。

首先 我們先求用1*2 的矩形拼成 n*m的矩形有多少種拼法

當n*m為奇數時,一定是不會拼出來的,因為想要拼出來就需要整數倍的小矩形數目。

為了加速算法,要把m,n中小的那個當做列

分兩個步驟:1) 先求出相鄰兩行的轉化關系

            2) 通過相鄰兩行的轉化關系算出經過n次轉化有幾種方法能拼成n*m的矩陣

1) 狀態標記 橫放和豎放的下一個均為1,豎放的上一個和不放置為0 ,每行可以轉化為1個2進制數。當這一行訪問結束時,就會得到上一行狀態,和該行狀態,因為所有情況都是我們設置的,所以pre狀態一定會轉化為now狀態

對於每一個位置,我們有三種放置方法:1. 豎直放置2. 水平放置3. 不放置
d為當前列號 ,初始化d, now, pre都為0。now為當前行,pre為當前行的上一行
1. d = d + 1, now << 1 | 1, pre << 1;   // 豎直放置,當前行該列為1,上一行該列置為為0
2. d = d + 2, now << 2 | 3, pre<< 2 | 3;  // 橫放 都為11
3. d = d + 1, now << 1, pre<< 1 | 1;    // 上一行該列置為1,不能豎放,不放置的狀態
因為轉移狀態有很多種,所以用dfs去枚舉各種可行的狀態。

下面是dfs實現:

 

\


2) 求出來相鄰兩行之間的狀態轉化,下面就要求經過n次轉化後最後狀態為(1<<m - 1) 的總數,對於n比較小(可用矩陣存儲) 的時候可用

 

\

當n很大的時候,就不能用上述的方法算了,這個時候矩陣的優勢就體現出來了

同樣是求經過n次轉化,從初始態到終態有幾種轉化法

建立矩陣的方法很簡單,矩陣的大小為(1<<m-1) 如過pre狀態能到達狀態now,那麼++matrix[pre][now]; 然後求此矩陣的n次冪即可

1、poj2411 題意:給定一個長寬小於等於11的矩形,問用1×2的小矩形填滿,有多少種方法。

[cpp]
#include <iostream>  
#include <cstdio>  
#include <cstring>  
#define LL long long  
using namespace std; 
const int maxn=13; 
int w,h,tan; 
LL dp[13][2100];//1<<11  
int path[14000][2];//11*(1<<11)  
void dfs(int l,int now,int pre) 

    if(l>w)return; 
    if(l==w) 
    { 
        path[tan][0]=pre; 
        path[tan++][1]=now; 
        return ;     
    } 
    dfs(l+2,(now<<2)|3,(pre<<2)|3); 
    dfs(l+1,(now<<1)|1,pre<<1); 
    dfs(l+1,now<<1,(pre<<1)|1); 

int main() 

    while(~scanf("%d%d",&h,&w)) 
    { 
        if(!h&&!w)break; 
        if(h<w){int t=h;h=w;w=t;} 
        tan=0; 
        dfs(0,0,0); 
        memset(dp,0,sizeof(dp)); 
        dp[0][(1<<w)-1]=1; 
        for(int i=0;i<h;++i) 
        { 
            for(int j=0;j<tan;++j) 
            { 
                dp[i+1][path[j][1]]+=dp[i][path[j][0]]; 
            } 
        } 
        printf("%lld\n",dp[h][(1<<w)-1]); 
    } 
    return 0; 

#include <iostream>
#include <cstdio>
#include <cstring>
#define LL long long
using namespace std;
const int maxn=13;
int w,h,tan;
LL dp[13][2100];//1<<11
int path[14000][2];//11*(1<<11)
void dfs(int l,int now,int pre)
{
 if(l>w)return;
 if(l==w)
 {
  path[tan][0]=pre;
  path[tan++][1]=now;
  return ; 
 }
 dfs(l+2,(now<<2)|3,(pre<<2)|3);
 dfs(l+1,(now<<1)|1,pre<<1);
 dfs(l+1,now<<1,(pre<<1)|1);
}
int main()
{
 while(~scanf("%d%d",&h,&w))
 {
  if(!h&&!w)break;
  if(h<w){int t=h;h=w;w=t;}
  tan=0;
  dfs(0,0,0);
  memset(dp,0,sizeof(dp));
  dp[0][(1<<w)-1]=1;
  for(int i=0;i<h;++i)
  {
   for(int j=0;j<tan;++j)
   {
    dp[i+1][path[j][1]]+=dp[i][path[j][0]];
   }
  }
  printf("%lld\n",dp[h][(1<<w)-1]);
 }
 return 0;
}


2、poj2663 題意:給定1*2的小矩形,去拼接一個3*n(n<30)的矩形,問有多少種方案。

3、poj3420 題意:給定1*2的小矩形,去拼接一個4*n(n<10^9)的矩形,問有多少種方案。N這麼大遞推肯定是不行了,所以我們要用矩陣快速冪進行加速,這個轉移矩陣如何構造呢,我們可以直接用pre狀態轉移到now狀態采用鄰接矩陣的方式表述就好了。這個矩陣的大小為at[16][16],at[15][15]就是最後要求的狀態

[cpp]
#include <iostream>  
#include <cstdio>  
#include <cstring>  
#define LL long long  
using namespace std; 
struct mat{ 
    LL at[16][16]; 
}; 
mat dat; 
int n,mod; 
void dfs(int l,int now,int pre) 

    if(l>4)return; 
    if(l==4) 
    { 
        ++dat.at[pre][now]; 
        return; 
    } 
    dfs(l+1,(now<<1)|1,(pre<<1)); 
    dfs(l+1,(now<<1),(pre<<1)|1); 
    dfs(l+2,(now<<2)|3,(pre<<2)|3); 

mat mul(mat a,mat b) 

    mat c; 
    memset(c.at,0,sizeof(c.at)); 
    for(int i=0;i<16;++i) 
    { 
        for(int k=0;k<16;++k) 
        { 
            if(a.at[i][k]) 
            { 
                for(int j=0;j<16;++j) 
                { 
                    c.at[i][j]+=a.at[i][k]*b.at[k][j]; 
                    if(c.at[i][j]>=mod){c.at[i][j]%=mod;} 
                } 
            } 
        } 
    } 
    return c; 

mat expo(mat a,int k) 

    if(k==1)return a; 
    mat e; 
    memset(e.at,0,sizeof(e.at)); 
    for(int i=0;i<16;++i){e.at[i][i]=1;} 
    if(k==0)return e; 
    while(k) 
    { 
        if(k&1)e=mul(a,e); 
        a=mul(a,a); 
        k>>=1; 
    } 
    return e; 

int main() 

    memset(dat.at,0,sizeof(dat.at)); 
    dfs(0,0,0); 
    while(~scanf("%d%d",&n,&mod)) 
    { 
        if(!n&&!mod)break; 
        if(mod==1){printf("0\n");continue;} 
        mat ans=expo(dat,n); 
        printf("%lld\n",ans.at[15][15]);     
    } 
    return 0; 

#include <iostream>
#include <cstdio>
#include <cstring>
#define LL long long
using namespace std;
struct mat{
 LL at[16][16];
};
mat dat;
int n,mod;
void dfs(int l,int now,int pre)
{
 if(l>4)return;
 if(l==4)
 {
  ++dat.at[pre][now];
  return;
 }
 dfs(l+1,(now<<1)|1,(pre<<1));
 dfs(l+1,(now<<1),(pre<<1)|1);
 dfs(l+2,(now<<2)|3,(pre<<2)|3);
}
mat mul(mat a,mat b)
{
 mat c;
 memset(c.at,0,sizeof(c.at));
 for(int i=0;i<16;++i)
 {
  for(int k=0;k<16;++k)
  {
   if(a.at[i][k])
   {
    for(int j=0;j<16;++j)
    {
     c.at[i][j]+=a.at[i][k]*b.at[k][j];
     if(c.at[i][j]>=mod){c.at[i][j]%=mod;}
    }
   }
  }
 }
 return c;
}
mat expo(mat a,int k)
{
 if(k==1)return a;
 mat e;
 memset(e.at,0,sizeof(e.at));
 for(int i=0;i<16;++i){e.at[i][i]=1;}
 if(k==0)return e;
 while(k)
 {
  if(k&1)e=mul(a,e);
  a=mul(a,a);
  k>>=1;
 }
 return e;
}
int main()
{
 memset(dat.at,0,sizeof(dat.at));
 dfs(0,0,0);
 while(~scanf("%d%d",&n,&mod))
 {
  if(!n&&!mod)break;
  if(mod==1){printf("0\n");continue;}
  mat ans=expo(dat,n);
  printf("%lld\n",ans.at[15][15]); 
 }
 return 0;
}


 

  1. 上一頁:
  2. 下一頁:
Copyright © 程式師世界 All Rights Reserved