[Hdu1693]Eat the Trees（插头DP）

Description

题意：在n*m(1<=N, M<=11 )的矩阵中，有些格子有树，没有树的格子不能到达，找一条或多条回路，吃完所有的树，求有多少种方法。

Solution

插头DP入门题，\(dp[i][j][k]\)表示\(G_{i,j}\)且轮廓线状态为\(k\)时的方案数

转移有6种，

Code

#include <cstdio>

#include <cstring>

#include <algorithm>

#define N 14

#define ll long long

using namespace std;

int T,n,m,g[N][N];

ll dp[N][N][1<<N];

inline int read(){

	int x=0,f=1;char ch=getchar();

	while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}

	while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}

	return x*f;

}

int main(){

	T=read();

	for(int ca=1;ca<=T;++ca){

		memset(g,0,sizeof(g));

		memset(dp,0,sizeof(dp));

		n=read(),m=read();

		for(int i=1;i<=n;++i)for(int j=1;j<=m;++j)g[i][j]=read();

		dp[0][m][0]=1;

		for(int i=1;i<=n;++i){

			for(int j=0;j<(1<<m);++j)//轮廓线最后一个一定是1，所以(1<<m)

				dp[i][0][j<<1]=dp[i-1][m][j];

			for(int j=1;j<=m;++j)

				for(int S=0;S<(1<<(m+1));++S){//状态有m+1位

					int x=1<<(j-1),y=1<<j;

					if(g[i][j]){

						if((S&x)!=0&&(S&y)!=0)//不是(==1)！,是(!=0)

							dp[i][j][S]=dp[i][j-1][S-x-y];

						else if((S&x)==0&&(S&y)==0)

							dp[i][j][S]=dp[i][j-1][S+x+y];

						else dp[i][j][S]=dp[i][j-1][S^x^y]+dp[i][j-1][S];

					}else {

						if(!(S&x)&&!(S&y))

							dp[i][j][S]=dp[i][j-1][S];

						else dp[i][j][S]=0;

					}

				}

		}

		printf("Case %d: There are %lld ways to eat the trees.\n",ca,dp[n][m][0]);

	}

	return 0;

}

巴特西

[Hdu1693]Eat the Trees（插头DP）

Description

Solution

Code

最新文章

热门文章