【轮廓线DP】POJ2411-Mondriaan's Dream

今天美国的院士过来讲课XD以为会很无聊但是谜之好听，而且英语基本上都听懂了的样子♪(´▽｀)

逃到图书馆来写解题报告

【题目大意】

给出一个m*n的方格，用2*1的骨牌覆盖有几种情况。

【思路】

最基础的轮廓线DP。分为三种情况：

（1）向上放，必须要满足上面的格子没有被放，且当前不在首行。→新状态=旧状态删去首位，末尾为1；

（2）向左放，必须要满足左边的格子和上面的格子都没有放，且当前不在首列。→新状态=旧状态删去首位，末两位微1；

（3）不放，必须满足上面的格子没有放。新状态=旧状态删去首位，末尾为0。

*轮廓线状压的表示不是按照纵坐标大小从左到右，而是按照从左到右，从上至下的顺序(K4..K0)来的:D

【错误点】

一开始把cur的变换写到最里面一重循环去了orz

 #include<iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 using namespace std;

 typedef long long ll;

 const int MAXN=;

 ll dp[][<<MAXN];

 void solve(int m,int n)

 {

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

     int cur=;

     memset(dp,,sizeof(dp));

     dp[cur][(<<n)-]=;

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

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

         {

             cur^=;

             /*cur要放在第二重循环后面，一开始写在了三重循环里面*/

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

             /*不要忘了要清空当前状态*/

             for (int k=;k<=(<<n)-;k++)

             {

                 //上放

                 if (i!= && !(k&(<<(n-))))

                 {

                     int now=(((k<<)|)&((<<n)-));

                     dp[cur][now]+=dp[-cur][k];

                 }

                 //不放

                 if (k&(<<(n-)))

                 {

                     int now=((k<<)&((<<n)-));

                     dp[cur][now]+=dp[-cur][k];

                 }

                 //左放

                 if (j!= && (k&(<<(n-))) && !(k&))

                 {

                     int now=(((k<<)|)&((<<n)-));

                     dp[cur][now]+=dp[-cur][k];

                 }

             }

         }

     cout<<dp[cur][(<<n)-]<<endl;

 }

 int main()

 {

     int m,n;

     while (scanf("%d%d",&m,&n))

     {

         if (m==n && n==) break;

         solve(m,n);

     }

     return ;

 }