hdu 1693 插头dp入门

hdu1693 Eat the Trees

题意

在\(n*m\)的矩阵中，有些格子有树，没有树的格子不能到达，找一条或多条回路，吃完所有的树，求有多少种方法。

解法

这是一道插头dp的入门题，只需要考虑插头的有无，不需要维护连通性，很愉快。

代码

#include <cstring>

#include <cstdio>

#include <cstdlib>

#define del(a,b) memset(a,sizeof(a),b)

using namespace std;

typedef long long ll;

int G[13][13];

ll dp[13][13][1<<12];

int n,m;

void 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 up=1<<j;

				int lef=1<<(j-1);

				if(G[i][j]) {

					if((k&up)&&(k&lef))

						dp[i][j][k]=dp[i][j-1][k^up^lef];

					else if(!(k&up)&&!(k&lef))

							dp[i][j][k]=dp[i][j-1][k|up|lef];

					else dp[i][j][k]=dp[i][j-1][k^up^lef]+dp[i][j-1][k];

				}

				else {

					if(!(k&up)&&!(k&lef))

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

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

				}

			}

		}

	}

}

int main() {

	int t;

	scanf("%d",&t);

	for(int k=1;k<=t;k++) {

		del(G,0);

		del(dp,0);

		scanf("%d %d",&n,&m);

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

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

			scanf("%d",&G[i][j]);

		DP();

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

	}

	return 0;

}

巴特西

hdu 1693 插头dp入门

hdu1693 Eat the Trees

题意

解法

代码

最新文章

热门文章