poj 2411 Mondriaan's Dream （轮廓线DP）

题意：有一个n*m的棋盘，要求用1*2的骨牌来覆盖满它，有多少种方案？（n<12，m<12）

思路：

　　由于n和m都比较小，可以用轮廓线，就是维护最后边所需要的几个状态，然后进行DP。这里需要维护的状态数就是min(n,m)。即大概是一行的大小。每次放的时候，只考虑（1）以当前格子为右方，进行横放；（2）以当前格子为下方进行竖放；（3）还有就是可以不放。

　　3种都是不一样的，所以前面的一种状态可能可以转为后面的几种状态，只要满足了条件。条件是，横放时，当前格子不能是最左边的；竖放时，当前格子不能是最上边的。而且要放的时候，除了当前格子，另一个格子也是需要为空才行的。

 //#include <bits/stdc++.h>

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #define pii pair<int,int>

 #define INF 0x3f3f3f3f

 #define LL long long

 using namespace std;

 const int N=1e5+;

 LL dp[][<<];

 LL cal(int n,int m)

 {

     if(n<m)     swap(n,m);

     memset(dp, , sizeof(dp));

     dp[][(<<m)-]=;

     int cur=;

     int h=(<<(m-));

     for(int i=; i<n; i++)

     {

         for(int k=; k<m; k++)

         {

             cur^=;

             memset(dp[cur], , sizeof(dp[cur]));

             for(int j=; j<(<<m); j++)

             {

                 if( j&h )            dp[cur][(j^h)<<]+=dp[cur^][j];          //最高位为1时，可以不放

                 if( k && !(j&) && (h&j))  dp[cur][((j&(h-))<<)|]+=dp[cur^][j];      //放横，左边为0，上面为1

                 if( i && !(h&j) )         dp[cur][(j<<)|]+=dp[cur^][j];      //放竖，上面为0

             }

         }

     }

     return dp[cur][(<<m)-];

 }

 int main()

 {

     freopen("input.txt", "r", stdin);

     int n, m;

     while(scanf("%d%d",&n,&m), n+m)    printf("%lld\n", cal(n,m));

     return ;

 }

AC代码

　　UVA一样的题：http://acm.hust.edu.cn/vjudge/problem/viewProblem.action?id=33787

 //#include <bits/stdc++.h>

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #define pii pair<int,int>

 #define INF 0x3f3f3f3f

 #define LL long long

 using namespace std;

 const int N=;

 LL dp[][<<N];

 LL cal(int n,int m)

 {

     if(n<m)     swap(n,m);

     memset(dp, , sizeof(dp));

     dp[][(<<m)-]=;

     int cur=, h=(<<(m-));

     for(int i=; i<n; i++)

     {

         for(int k=; k<m; k++)

         {

             cur^=;

             for(int j=; j<(<<m); j++) dp[cur][j]=;

             for(int j=; j<(<<m); j++)

             {

                 if( j&h )                  dp[cur][(j^h)<<]+=dp[cur^][j];          //最高位为1时，可以不放

                 if( k && !(j&) && (h&j))  dp[cur][((j&(h-))<<)|]+=dp[cur^][j];  //放横，左边为0，上面为1

                 if( i && !(h&j) )          dp[cur][(j<<)|]+=dp[cur^][j];          //放竖，上面为0

             }

         }

     }

     return dp[cur][(<<m)-];

 }

 int main()

 {

     //freopen("input.txt", "r", stdin);

     int n, m;

     while(~scanf("%d%d",&n,&m))    printf("%lld\n", cal(n,m));

     return ;

 }

AC代码