menu ZigZagK的博客
account_circle

正在努力加载中QAQ

[插头DP]HDU1693【Eat the Trees】题解
apps HDU
local_offer 查看标签
comment 0 条评论

题目概述

给出 $n\times m$ 的网格图,其中有些格子是障碍,求有多少种方法用若干个哈密顿回路覆盖没有障碍的格子。

解题报告

万年神坑插头DP,插头DP可以解决棋盘上的一些连通性问题(比如这题)。插头指的是一个格子与周围格子的连通情况,插头DP通过记录轮廓线上的插头状态来进行转移。

插头DP

因为转移时轮廓线上只有两个位置的状态改变了,所以我们只需要关注这两个位置:

转移

由于可以用若干条哈密顿回路,观察之后我们发现只需要知道这两个位置上是否连有插头即可,就可以进行转移:

  1. A有插头,B有插头:当前格子一定有上插头和左插头,否则连不起来。
  2. A有插头,B没有插头:当前格子一定有左插头,还可以有右插头或下插头(取决于右边或者下面是不是障碍,且不能同时有右插头和下插头),不能有上插头。
  3. A没有插头,B有插头:当前格子一定有上插头,还可以有右插头或下插头(取决与右边或者下面是不是障碍,且不能同时有右插头和下插头),不能有左插头。
  4. A没有插头,B没有插头:当前格子一定有右插头和下插头,因为每个格子都有两个插头。

还有障碍格子的转移问题,因为障碍格子不能连进来也不能连出去,所以直接传递就行了。

示例程序

#include<cstdio>
using namespace std;
typedef long long LL;
const int maxn=11,maxs=1<<maxn+1;

int te,n,m,pic[maxn+5][maxn+5];LL f[2][maxn+5][maxs];

int main(){
    freopen("program.in","r",stdin);freopen("program.out","w",stdout);
    for (int t=(scanf("%d",&te),1);t<=te;t++){
        scanf("%d%d",&n,&m);for (int i=1;i<=n;i++) for (int j=1;j<=m;j++) scanf("%d",&pic[i][j]);
        for (int s=0;s<(1<<m+1);s++) f[0][m][s]=0;f[0][m][0]=1;
        for (int i=1,c=1;i<=n;i++,c^=1){
            for (int j=0;j<=m;j++) for (int s=0;s<(1<<m+1);s++) f[c][j][s]=0;
            for (int s=0;s<(1<<m+1);s++) if (f[c^1][m][s]) f[c][0][s<<1]=f[c^1][m][s];
            for (int j=1;j<=m;j++)
                for (int s=0;s<(1<<m+1);s++){
                    LL F=f[c][j-1][s];bool A=s>>j-1&1,B=s>>j&1;
                    if (!pic[i][j]) {if (!A&&!B) f[c][j][s]+=F;}
                    else if (A&&B) f[c][j][s^(1<<j-1)^(1<<j)]+=F;
                    else if (A&&!B){
                        if (pic[i][j+1]) f[c][j][s^(1<<j-1)^(1<<j)]+=F;
                        if (pic[i+1][j]) f[c][j][s]+=F;
                    } else if (!A&&B){
                        if (pic[i][j+1]) f[c][j][s]+=F;
                        if (pic[i+1][j]) f[c][j][s^(1<<j-1)^(1<<j)]+=F;
                    } else if (pic[i][j+1]&&pic[i+1][j]) f[c][j][s^(1<<j-1)^(1<<j)]+=F;
                }
        }
        printf("Case %d: There are %lld ways to eat the trees.\n",t,f[n&1][m][0]);
    }
    return 0;
}
版权声明:本博客所有文章除特别声明外,均采用 CC BY 4.0 CN协议 许可协议。转载请注明出处!
名称不能为空
email
邮箱不能为空,请填写正确格式
link
网址请用http://或https://开头
message
评论不能为空
资瓷Markdown和LaTeX数学公式
sentiment_very_satisfied
keyboard_arrow_up