随笔 - 68  文章 - 57  trackbacks - 0
<2011年3月>
272812345
6789101112
13141516171819
20212223242526
272829303112
3456789

常用链接

留言簿(8)

随笔分类(74)

随笔档案(68)

搜索

  •  

最新评论

阅读排行榜

评论排行榜

这个题目去年就过了,用得是状态压缩dp,不过没用dfs预处理,当时做得不是很明白,还是参考网上的一个代码做的。
现在重新做了一下这个题目,请教了icecream,学会了一个很简练的做法,而且比较好理解还好写。
首先还是状态的表示,用0表示没有放木块,用1表示放了木块。此外,对于一个横放的木块,对应的两位都用1表示;对于一个竖放的木块,第一行用1表示,第二行用0表示。这只是一种设状态的方式,当然还有别的设法,但是这种方法在接下来就会发现优点。

状态表示完就要处理转移了,如何判断一个转移是否合法比较难办,用一个dfs却可以简洁的解决这个问题。
对于上一行到下一行的转移,规定上一行一定填满,这样有三种方式:
    dfs(col + 1, (s1 << 1) | 1, s2 << 1, n);
    dfs(col + 1, s1 << 1, (s2 << 1) | 1, n);
    dfs(col + 2, (s1 << 2) | 3, (s2 << 2) | 3, n);
第一种上面是1,那么下面一定是0,表示是一个竖放的木块。
第二种上面是0,就是说这个位置一定是一个竖放木块的下半截,那么下一行肯定是要另起一行了,放一个竖放或者横放的木块都必须是1。
第三种相当于上下两行各放一个横木块。
实现的时候我用了一个vector记录每个状态所有可行的转移,这样在dp的时候可以加快一些效率。

还有一个问题需要考虑,那就是初值和最终的结果。如果寻找合法状态,依然比较麻烦,假设共有n行,可以分别在这n行上下新加两行。下面一行都是1,由于第n行肯定要填满,这样新加的全1的行就相当于顶住了第n行使其没有凸出(有凸出那么第n+1行有0),而通过第n行到第n+1行转移保留了所有合法状态;同理最上面加的那行保证第一行没有凸出。最后第n+1行对应全1的状态就是最终的结果了。通过新加行巧妙地解决了初值和终值。

实现的时候也需要注意一下,在TSP问题中,外层循环是状态,内层是点,之所以这样写因为在枚举点的时候,可能会从比当前编号大的点转移,但是由于无论怎样转移过来的状态肯定比当前状态小(去掉了1),所以先从小到大枚举状态就保证转移过来的状态一定是算过的。而这个题目里面正好反过来,因为状态可能从比当前状态大的状态转移过来,而行数肯定是从编号小的行转移,因此先枚举行就能保证转移过来的状态一定是更新过的。


#include <cstdio>
#include 
<vector>
#include 
<algorithm>
using namespace std;
const int N = 11;

vector
<int> g[1<<N];
long long dp[N+2][1<<N];

void dfs(int col, int s1, int s2, int n)
{
    
if (col >= n)
    {
        
if (s1 < (1 << n) && s2 < (1 << n))
            g[s2].push_back(s1);
        
return;
    }
    dfs(col 
+ 1, (s1 << 1| 1, s2 << 1, n);
    dfs(col 
+ 1, s1 << 1, (s2 << 1| 1, n);
    dfs(col 
+ 2, (s1 << 2| 3, (s2 << 2| 3, n);
}
long long calc(int m, int n)
{
    
if (m < n)  swap(m, n);
    dfs(
000, n);
    
int state = 1 << n;

    dp[
0][0= 1;
    
for (int i = 1; i <= m + 1; i++)
        
for (int s = 0; s < state; s++)
            
for (int j = 0; j < g[s].size(); j++)
                dp[i][s] 
+= dp[i-1][g[s][j]];
    
return dp[m+1][state-1];
}

int main()
{
    
int m, n;

    
while (scanf("%d %d"&m, &n) == 2)
    {
        
if (m == 0 && n == 0)
            
break;
        
for (int i = 0; i < (1 << N); i++)
            g[i].clear();
        memset(dp, 
0sizeof(dp));
        printf(
"%I64d\n", calc(m, n));
    }

    
return 0;
}
posted on 2009-07-31 08:12 sdfond 阅读(2311) 评论(1)  编辑 收藏 引用 所属分类: Algorithm - Dynamic Programming

FeedBack:
# re: POJ 2411 Mondriaan's Dream 2011-03-17 12:00 Alaskan
请问一下,
dfs(col + 1, (s1 << 1) | 1, s2 << 1, n);
dfs(col + 1, s1 << 1, (s2 << 1) | 1, n);
dfs(col + 2, (s1 << 2) | 3, (s2 << 2) | 3, n);
中的s1,s2参数是指什么,为什么这样做位运算?  回复  更多评论
  

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   博问   Chat2DB   管理