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ǎ崽 閱讀(1670)
評論(2) 編輯 收藏 引用