http://acm.hdu.edu.cn/showproblem.php?pid=1693
昨天做长亮杯的题目遇到这道，请教了zjfc3大大
知道是【基于连通性的状态压缩动态规划问题】
给了我08国家集训队陈丹琦的论文(cdq竟然是女生。。Orz，无限崇拜)
看了知道了插头和轮廓线的概念
不过论文里说的是一条回路用三进制表示。。。
这题用二进制(有没有插头)表示就可以。。
画了一个晚上的图，终于知道怎么处理了。。
不过实现起来比较反
参考了zjfc3大大的程序
终于明白，感慨位运算的强大阿~~
#include<stdio.h>
#include<string>
#include<stdlib.h>
int map[11][11];
__int64 dp[2][1<<12];
int main()
{
int T,n,m,i,j,roll,ROLL,cas;
scanf("%d",&T);
for(cas=1;cas<=T;cas++)
{
scanf("%d%d",&n,&m);
for(i=0;i<n;i++)
for(j=0;j<m;j++)
scanf("%d",&map[i][j]);
ROLL = 1;
memset(dp[ROLL],0,sizeof(dp[ROLL]));
dp[ROLL][0] = 1;
for(i=0;i<n;i++)
{
int len = 1<<m;
roll = ROLL ^ 1;
memset(dp[roll],0,sizeof(dp[roll]));
for(j=0;j<len;j++)
dp[roll][j<<1] = dp[ROLL][j];
ROLL = roll;
for(j=0;j<m;j++)
{
roll = ROLL ^ 1;
int len = 1<<m<<1;
for(int k=0;k<len;k++)
{
int p = 1<<j<<1;
int q = 1<<j;
bool a = p&k;
bool b = q&k;
if(map[i][j])
{
dp[roll][k] = dp[ROLL][k^p^q];
if(a!=b)
dp[roll][k] += dp[ROLL][k];
}
else
{
if(a==0 && b==0)
dp[roll][k] = dp[ROLL][k];
else
dp[roll][k] = 0;
}
}
ROLL = roll;
}
}
printf("Case %d: There are %I64d ways to eat the trees.\n",cas,dp[roll][0]);
}
return 0;
}
posted on 2009-03-24 11:26
shǎ崽 阅读(1665)
评论(2) 编辑 收藏 引用