状压DP POJ 2411 Mondriaan'sDream

约定不等于承诺〃 2021-12-23 09:17 241阅读 0赞

[题目传送门][Link 1]

1 /*
     2     题意：一个h*w的矩阵（1<=h,w<=11），只能放1*2的模块，问完全覆盖的不同放发有多少种？
     3     状态压缩DP第一道：dp[i][j] 代表第i行的j状态下的种数(状态即为二进制10101110101...的样子)
     4                         横着的定义为11，竖着的定义为01，当两行的状态已填满并且没有出现奇数个1时，累加个数
     5                             即两行状态相或要全为1，两行相与要没有连续的1的个数是奇数个
     6 */
     7 #include <cstdio>
     8 #include <iostream>
     9 #include <algorithm>
    10 #include <cmath>
    11 #include <cstring>
    12 #include <map>
    13 using namespace std;
    14 
    15 const int MAXN = 1e4 + 10;
    16 const int INF = 0x3f3f3f3f;
    17 long long dp[20][3010];
    18 
    19 bool ok(int x)
    20 {
    21     int res = 0;
    22     while (x)
    23     {
    24         if (x & 1)  res++;
    25         else
    26         {
    27             if (res & 1)    return false;
    28             res = 0;
    29         }
    30 
    31         x >>= 1;
    32     }
    33     if (res & 1)    return false;
    34     else    return true;
    35 }
    36 
    37 int main(void)      //POJ 2411 Mondriaan'sDream
    38 {
    39     #ifndef ONLINE_JUDGE
    40     freopen ("A.in", "r", stdin);
    41     #endif
    42 
    43     int n, m;
    44     while (~scanf ("%d%d", &n, &m) && n && m)
    45     {
    46         memset (dp, 0, sizeof (dp));
    47         int tot = (1 << m);
    48         for (int i=0; i<tot; ++i)
    49         {
    50             if (ok (i)) dp[1][i] = 1;
    51         }
    52 
    53         for (int i=1; i<=n-1; ++i)
    54         {
    55             for (int j=0; j<tot; ++j)
    56             {
    57                 if (dp[i][j])
    58                 {
    59                     for (int k=0; k<tot; ++k)
    60                     {
    61                         if ((j | k) == tot - 1 && ok (j & k))
    62                         {
    63                             dp[i+1][k] += dp[i][j];
    64                         }
    65                     }
    66                 }
    67             }
    68         }
    69 
    70         printf ("%I64d\n", dp[n][tot-1]);
    71     }
    72 
    73     return 0;
    74 }

转载于:https://www.cnblogs.com/Running-Time/p/4368515.html

[Link 1]: http://poj.org/problem?id=2411