ZigZagK的博客
[插头DP]HDU1693【Eat the Trees】题解
[插头DP]HDU1693【Eat the Trees】题解
2019年2月9日 19:59
HDU
查看标签

题目概述

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

解题报告

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

插头DP

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

转移

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

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

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

示例程序

  • 1
  • 2
  • 3
  • 4
  • 5
  • 6
  • 7
  • 8
  • 9
  • 10
  • 11
  • 12
  • 13
  • 14
  • 15
  • 16
  • 17
  • 18
  • 19
  • 20
  • 21
  • 22
  • 23
  • 24
  • 25
  • 26
  • 27
  • 28
  • 29
  • 30
  • 31
  • 32
  • 33
#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协议 许可协议。转载请注明出处!
本文写于 2246 天前,最后更新于 2246 天前。
部分信息可能已经过时,博主也可能已经无法对其内容进行解答。
OK
  1. 1 Skyscape Plum - Melodic Artist
  2. 2 ほしのおとしもの ああああ
  3. 3 感情の摩天楼 ~ Cosmic Mind 上海アリス幻樂団
  4. 4 秘匿されたフォーシーズンズ 上海アリス幻樂団
  5. 5 Ideal and the Real 小西利樹
  6. 6 Undertale Toby Fox
  7. 7 First Steps Lena Raine
  8. 8 Mirror Temple (Mirror Magic Mix) Lena Raine / 2 Mello
  9. 9 City of Tears Christopher Larkin
  10. 10 Tower Of Heaven (You Are Slaves) Feint
Skyscape - Plum - Melodic Artist
00:00 / 00:00
An audio error has occurred, player will skip forward in 2 seconds.

作曲 : Jeong Min Jae

纯音乐,请欣赏