首页 > 代码库 > SGU 132. Another Chocolate Maniac

SGU 132. Another Chocolate Maniac

题意:有1*2的小方块,在n*m (n <= 70, m <= 7)的棋盘内有一些点不能覆盖,要求将方块最少数量地放入棋盘,使得空格子两两不相邻。

m那么小,很明显是状态压缩DP对吧。

我们用f[i][j]表示在第i行,覆盖前一部分后当前状态为j的最小花费,转移是很显然的。重点是状态之间的关系如何确定,否则无法进行转移。考虑预处理出融洽的两个状态。用1表示在当前位放置了一块方块,我们从0枚举到(1 << m) - 1,我们要判断两个决策是否融洽,但是问题来了:棋盘上有不可覆盖点!!其实无所谓吧,我们可以尝试不预处理,而是在转移时枚举状态。复杂度:O(n*s*s)。好像没了??2维数组真的够了么???当然不行啊!因为一个方块可以同时影响两行的状态,所以我们要改进状态表示,用三维数组吧。。。然后被细节问题坑成狗。空间卡的死,需要用滚动数组优化。dfs实现时,其实只要考虑好各种情况就行了。

  1  //{HEADS  2 #define FILE_IN_OUT  3 #include <cstdio>  4 #include <cstring>  5 #include <cstdlib>  6 #include <cmath>  7 #include <ctime>  8 #include <algorithm>  9 #include <iostream> 10 #include <fstream> 11 #include <vector> 12 #include <stack> 13 #include <queue> 14 #include <deque> 15 #include <map> 16 #include <set> 17 #include <bitset> 18 #include <complex> 19 #include <string> 20 #define REP(i, j) for (int i = 1; i <= j; ++i) 21 #define REPI(i, j, k) for (int i = j; i <= k; ++i) 22 #define REPD(i, j) for (int i = j; 0 < i; --i) 23 #define STLR(i, con) for (int i = 0, sz = con.size(); i < sz; ++i) 24 #define STLRD(i, con) for (int i = con.size() - 1; 0 <= i; --i) 25 #define CLR(s) memset(s, 0, sizeof s) 26 #define SET(s, v) memset(s, v, sizeof s) 27 #define mp make_pair 28 #define pb push_back 29 #define PL(k, n) for (int i = 1; i <= n; ++i) { cout << k[i] << ‘ ‘; } cout << endl 30 #define PS(k) STLR(i, k) { cout << k[i] << ‘ ‘; } cout << endl 31 using namespace std; 32 void FILE_INIT(string FILE_NAME) { 33 #ifdef FILE_IN_OUT 34 #ifndef ONLINE_JUDGE  35     freopen((FILE_NAME + ".in").c_str(), "r", stdin); 36     freopen((FILE_NAME + ".out").c_str(), "w", stdout); 37 #endif 38 #endif 39 } 40 typedef long long LL; 41 typedef double DB; 42 typedef pair<int, int> i_pair; 43 const int INF = 0x3f3f3f3f; 44 const LL INFL = 0x3f3f3f3f3f3f3f3f; 45 //} 46  47 char gchar() { 48     char ret = getchar(); 49     for(; ret != . && ret != *; ret = getchar()); 50     return ret; 51 } 52  53 const int maxn = 74; 54 const int maxs = (1 << 7) + 3; 55 int G[maxn]; 56 int n, m, now, last; 57  58 LL f[2][maxs][maxs]; 59 int Snum; 60  61 //最好玩的部分开始!! 62 void dfs(int col, int pre_s, int now_s, int next_s, int cnt, LL f_last) { 63 f(0 < col && !(pre_s & (1 << (col - 1))) && !(now_s & (1 << (col - 1)))) { 64         return ; 65     } 66     if(1 < col && !(now_s & (1 << (col - 1))) && !(now_s & (1 << (col - 2)))) { 67         return ; 68     } 69     if(col == m) { 70         f[now][now_s][next_s] = min(f[now][now_s][next_s], f_last + cnt); 71         return ; 72     } 73     dfs(col + 1, pre_s, now_s, next_s, cnt, f_last); 74     if(!(now_s & (1 << (col))) && !(next_s & (1 << (col)))) { 75         dfs(col + 1, pre_s, now_s | (1 << (col)), next_s | (1 << (col)), cnt + 1, f_last); 76     } 77     if(col + 1 < m && !(now_s & (1 << col)) && !(now_s & (1 << (col + 1)))) { 78         dfs(col + 1, pre_s, now_s | (1 << (col)) | (1 << (col + 1)), next_s, cnt + 1, f_last); 79     } 80 } 81 int main() { 82     FILE_INIT("132"); 83  84     scanf("%d%d", &n, &m) 85     for(int i = 1; i <= n; ++i) { 86         for(int j =  0; j < m; ++j) { 87             char c = gchar(); 88             if(c == *) { 89                 G[i] += 1 << j; 90             } 91         } 92     } 93     Snum = (1 << m) - 1; 94     now = 0, last = 1; 95     memset(f[now], INF, sizeof f[now]); 96     f[0][Snum][G[1]] = 0; 97     for(int i = 1; i <= n; ++i) { 98         swap(now, last); 99         memset(f[now], INF, sizeof f[now]);100         for(int j = 0; j <= Snum; ++j) {101             for(int k = 0; k <= Snum; ++k) {102                 if(f[last][j][k] < INFL) {103                     dfs(0, j, k, G[i + 1], 0, f[last][j][k]);104                 }105             }106         }107     }108     LL ans = INFL;109     for(int i = 0; i <= Snum; ++i) {110         ans = min(ans, f[now][i][0]);111     }112     printf("%lld\n", ans);113     return 0;114 }
View Code

送测试数据:

3 2....**4 4.**.*..**..*.**.7 7........................*........................8 1........1 1.3 3*.*...*.*3 7*.*.*....*...**...*.*2 7.....*.**..*.*1 7*.*.*..2 2*..*70 7..........................................................................................................................................................................................................................................................................................................................................................................................................................................................................................................10 3..*..*..*..*..**..*..*..*..*..10 4*..**..**..**..**..**..**..**..**..**..*10 3..*..*..*..*..*..*..*..*..*..*10 2....................5 5.*..**......**.**.*..**..
INOUT
2216301321016477774
OUTPUT

 

SGU 132. Another Chocolate Maniac