UVA - 11270 轮廓线DP

时间：2023-01-06 01:34:00

其实这题还能用状压DP解决，可是时间达到2000ms只能过掉POJ2411.状压DP解法详见状压DP解POJ2411

贴上POJ2411AC代码 ： 2000ms 时间复杂度h*w*(2^w)*(2^w)

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <utility>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define eps 1e-10
#define inf 0x3f3f3f3f
#define PI pair<int, int>
typedef long long LL;
const int maxn = 1 << 11;
LL dp[12][maxn];
int w, h;
bool TestFirstLine(int state) {
	for(int i = 0; i < w;) {
		int x = 1 << i;
		if((x & state) && i+1 < w && ((x << 1) & state)) {
			i += 2;
		}
		else if(!(x & state)) ++i;
		else return false;
	}
	return true;
}

bool is_ok(int state1, int state2) {
	for(int i = 0; i < w;) {
		int x = 1 << i;
		if(!(x & state1)) {
			if(!(x & state2)) return false;
			++i;
		}
		else {
			int y = x << 1;
			if(!(x & state2)) ++i;
			else if(x & state2) {
				if(i == w-1 || !(y & state1) || !(y & state2)) return false;
				i += 2;
			}
		}
	}
	return true;
}

LL solve() {
	if(h < w) swap(w, h);
	int r = 1 << w;
	memset(dp, 0, sizeof(dp));
	//边界
	for(int i = 0; i < r; ++i)
		if(TestFirstLine(i)) dp[0][i] = 1;
	for(int i = 1; i < h; ++i)
		for(int j = 0; j < r; ++j)
			for(int k = 0; k < r; ++k) {
				if(is_ok(j, k)) dp[i][j] += dp[i-1][k];
			}
	return dp[h-1][r-1];
}

int main() {
	while(scanf("%d%d", &w, &h) == 2 && w && h) {
		printf("%lld\n", solve());
	}
	return 0;
}

对于uva11270这种状压dp会超时，使用轮廓线DP可将复杂度降低到w*h*(2^w)，详细解法见训练指南P384

AC代码

#include <cstdio>
#include <cmath>
#include <algorithm>
#include <cstring>
#include <utility>
#include <string>
#include <iostream>
#include <map>
#include <set>
#include <vector>
#include <queue>
#include <stack>
using namespace std;
#pragma comment(linker, "/STACK:1024000000,1024000000")
#define eps 1e-10
#define inf 0x3f3f3f3f
#define PI pair<int, int>
typedef long long LL;
const int maxn = 10 + 1;
LL dp[2][1<<maxn];
int n, m;
void update(int f, int a, int b) {
	if(b & (1<<m)) dp[f][b^(1<<m)] += dp[1-f][a];
}
LL solve() {
	if(n < m) swap(n, m);
	memset(dp, 0, sizeof(dp));
	int f = 0;
	dp[0][(1<<m)-1] = 1; //边界
	for(int i = 0; i < n; ++i)
		for(int j = 0; j < m; ++j) {
			f ^= 1;
			memset(dp[f], 0, sizeof(dp[f]));
			for(int k = 0; k < (1 << m); ++k) {
				//不放
				update(f, k, k<<1);
				//横着放
				if(j && !(k&1)) update(f, k, (k<<1)^3);
				//竖着放
				if(i && !(k&(1<<m-1))) update(f, k, (k<<1)^(1<<m)^1);
			}
		}
	return dp[f][(1<<m)-1];
}
int main() {
	while(scanf("%d%d", &n, &m) == 2) {
		printf("%lld\n", solve());
	}
	return 0;
}

如有不当之处欢迎指出！

相关文章