首页 > 代码库 > 【HDU】1663 Eat the Trees

【HDU】1663 Eat the Trees

2024-09-05 03:19:56   217人阅读

题目链接：http://acm.hdu.edu.cn/showproblem.php?pid=1693

 

给出一块$r*c$的地，其中有的土地上种上了树，有些没有种上树，只能在种上树的地上走，通过走若干个回路，来走遍所有种树的土地。问有多少种走法。

 

插头DP。

　　既然可以走多个回路，似乎就不需要考虑括号序列合并的问题了，直接状压表示每一个位置有没有插头。

　　我写的转出。

　　1.如果当前点都没有上插头和左插头，那么插头无法延续，新建一个回路。

　　2.如果当前点都有上插头和左插头，回路在此处闭合。

　　3.如果上插头和左插头都只有一个，那么每一种状态有两种可以延续的方案。

 1 #include<iostream> 2 #include<cstdio> 3 #include<algorithm> 4 #include<vector> 5 #include<cstdlib> 6 #include<cmath> 7 #include<cstring> 8 using namespace std; 9 #define maxn 1310 #define llg long long 11 #define yyj(a) freopen(a".in","r",stdin),freopen(a".out","w",stdout);12 llg n,m,g[maxn][maxn];13 llg f[maxn][maxn][1<<(maxn+1)],T,tot;14 void dp()15 {16     memset(f,0,sizeof(f));17     tot=(1<<(m+1))-1;18     f[0][m][0]=1;19     for (llg i=1;i<=n;i++)20     {21         for (llg k=0;k<=tot;k++) f[i][0][k<<1]=f[i-1][m][k];22         for (llg j=0;j<m;j++)23         {24             llg le=(1<<(j)),up=(1<<(j+1));//分别表示上左插头所在状态中的位置25             for (llg k=0;k<=tot;k++)26             {27                 if (!g[i][j+1]) {if (!(k&le) && !(k&up)) f[i][j+1][k]=f[i][j][k]; continue;}28                 if (!(k&le) && !(k&up)) {f[i][j+1][k+le+up]+=f[i][j][k]; continue;}29                 if ((k&le) && (k&up)) {f[i][j+1][k-le-up]+=f[i][j][k]; continue;}30                 if (k&le) {f[i][j+1][k-le+up]+=f[i][j][k]; f[i][j+1][k]+=f[i][j][k];}31                 else {f[i][j+1][k-up+le]+=f[i][j][k]; f[i][j+1][k]+=f[i][j][k];}32             }33         }34     }35 //    cout<<f[n][m+1][0];36 }37 38 int main()39 {40     yyj("hdu1693");41     cin>>T;42     for (llg t=1;t<=T;t++)43     {44         scanf("%lld%lld",&n,&m);45         for (llg i=1;i<=n;i++) for (llg j=1;j<=m;j++) scanf("%lld",&g[i][j]);46         dp();47         printf("Case %lld: There are %lld ways to eat the trees.\n",t,f[n][m][0]);  48     }49     return 0;50 }

 

【HDU】1663 Eat the Trees


联系
我们