pku 2411 Mondriaan's Dream dp 状态压缩

我会带着你远行 2022-07-12 11:00 110阅读 0赞

以前没做过状态压缩的题目,今天是见识了,我看下下面这段精辟的话才做出来的. -\_-

本该很早就ac的题一直调到现在，why？这次真的是自己的状态很差的原因啊！

下午看了一份报告，其他人有dfs的方法，其中有个同学和我是思路一模一样，但是我的数据都没过，思路一开始就对的，错在一个很小的条件判断，很伤人啊，还以为自己的dp找错了呢!看来还要相信自己的实力的。

算法我觉得慢简单的，和我上午ac的一个题思路没什么区别，就是每行取二进制状态。

设dp\[i\]\[k\]为第i行状态值为k时的ways。那么找出它与第i-1行的状态之间的关系即可。

由于在做第i行dp时必须完全覆盖第i-1行，只要抓住这个条件不放就行。

1、如果第i行中有0，则第i-1行一定为1；

2、如果第i行中为1的x列第i-1行为0，说明第i行肯定是竖着放的；

3、如果第i行中为1的x列第i-1行的该列也为1，可能性只有一个，第i行是横放的，所以第i行的x+1列也必须为1，又因为第i行的x+1列为1是因为横着放的，所以第i-1行的x+1列也必须为1。

找到了关系就很简单了。哎呀，一想到这里我就不爽，本该恨早就ac的。

哦~，差点忘了，还有初始化的第1行，将它初始化为只存在横着或者不放。

本段原话引自: [http://gisyhy.blog.163.com/blog/static/129390343200992441558735/][http_gisyhy.blog.163.com_blog_static_129390343200992441558735]

ps: 原作者的代码写得很优美.哇咔咔.

\#include <stdio.h> \#include <string.h> \#include <stdlib.h> \#include <math.h> \#include <iostream> \#include <string> \#include <vector> \#include <queue> \#include <deque> \#include <list> \#include <algorithm> \#include <map> \#include <hash\_map> \#include <hash\_set> \#include <set> \#include <utility> using namespace std; long long dp\[11\]\[1<<11\]; int h, w; bool isOk(int s) \{ int i = 0; while(i < w) \{ if(s & (1<<i)) \{ if(i == w-1 || (s&(1<<(i+1))) == 0) return false; i += 2; \} else i++; \} return true; \} bool isOk(int s1, int s2) \{ int i = 0; while(i < w) \{ if(s1 & (1<<i)) \{ if((s2 & (1<<i)) == 0) i++; else \{ if(i == w-1 || ( (s1 & (1<<(i+1))) && (s2 & (1<<(i+1)))) == 0) return false; i += 2; \} \} else \{ if((s2&(1<<i)) == 0) return false; i++; \} \} return true; \} int main() \{ while(scanf("%d%d", &h, &w) , h&&w) \{ if(h < w) \{ int tmp = w; w = h; h = tmp; \} memset(dp, 0, sizeof(dp)); int MAX = (1<<w); for(int i = 0; i < MAX; ++i) if(isOk(i)) dp\[0\]\[i\] = 1; for(int i = 1; i < h; ++i) for(int j = 0; j < MAX; ++j) //line i for(int k = 0; k < MAX; ++k) //line i-1 if(isOk(j, k)) dp\[i\]\[j\] += dp\[i-1\]\[k\]; printf("%I64d/n", dp\[h-1\]\[MAX-1\]); \} return 0; \}

[http_gisyhy.blog.163.com_blog_static_129390343200992441558735]: http://gisyhy.blog.163.com/blog/static/129390343200992441558735/