首页 > 代码库 > hdu1693：eat trees(插头dp)

hdu1693：eat trees(插头dp)

2024-08-04 19:03:42   211人阅读

题目大意：

题目背景竟然是dota！屠夫打到大后期就没用了，，只能去吃树！

给一个n*m的地图，有些格子是不可到达的，要把所有可到达的格子的树都吃完，并且要走回路，求方案数

题解：

这题大概是最简单的插头dp了。。

比陈丹琦论文里的例题还要简单，因为允许有多个回路，所以不需要存储插头之间的连通性，直接二进制状压

搞清楚插头和轮廓线的概念基本就可以做出来了

这里有一些资料http://www.docin.com/p-741918386.html

代码：

#include <iostream>#include <stdio.h>#include<string.h>#include<algorithm>#include<string>#include<ctype.h>using namespace std;#define MAXN 10000long long dp[13][13][1<<13];int g[13][13];int n,m;int main(){    int t,cas=0;    scanf("%d",&t);    while(t--)    {        cas++;        scanf("%d%d",&n,&m);        for(int i=1;i<=n;i++)        {            for(int j=1;j<=m;j++)            {                scanf("%d",g[i]+j);            }        }        memset(dp,0,sizeof(dp));        dp[0][m][0]=1;        for(int i=1;i<=n;i++)        {            for(int j=0;j<(1<<m);j++)            {                dp[i][0][j<<1]=dp[i-1][m][j];            }            for(int j=1;j<=m;j++)            {                for(int k=0;k<(1<<(m+1));k++)                {                    int u=1<<j;                    int l=1<<(j-1);                    if(g[i][j]==0)                    {                        if((!(k&u))&&(!(k&l)))                            dp[i][j][k]=dp[i][j-1][k];                        continue;                    }                    if((k&u)&&(k&l))                    {                        dp[i][j][k-u-l]+=dp[i][j-1][k];                    }                    if((k&u)&&(!(k&l)))                    {                        dp[i][j][k]+=dp[i][j-1][k];                        dp[i][j][k-u+l]+=dp[i][j-1][k];                    }                    if((k&l)&&(!(k&u)))                    {                        dp[i][j][k]+=dp[i][j-1][k];                        dp[i][j][k-l+u]+=dp[i][j-1][k];                    }                    if((!(k&u))&&(!(k&l)))                    {                        dp[i][j][k+u+l]+=dp[i][j-1][k];                    }                }            }        }        printf("Case %d: There are %I64d ways to eat the trees.\n",cas,dp[n][m][0]);    }    return 0;}

 

hdu1693：eat trees(插头dp)


联系
我们