POJ-2836 : Rectangular Covering

問題概要

平面上にN(<15)個点がある。2個以上の点を含む軸に平行な面積正の長方形を重ねて全ての点をカバーしたい。最小面積を求める問題。ただし重複した部分の面積は重複した分数える。

解法

ビットDP。3点以上が角にくるような長方形がコーナーケースで前処理をかけておく必要がある。

acceptされたコード

計算量O(N^2*2^N)。

#include <cstdio>
#include <algorithm>
using namespace std;

const int MAX_N = 15;
const int INF = 1<<29;

int N;
int dp[1<<MAX_N];
int xs[MAX_N], ys[MAX_N];
int bs[MAX_N][MAX_N], area[MAX_N][MAX_N];

bool init(){
	scanf("%d", &N);
	for(int i=0; i<N; i++){
		scanf("%d%d", xs+i, ys+i);
	}

	return N > 0;
}

int solve(){
	fill(dp, dp+(1<<N), INF);
	dp[0] = 0;

	for(int i=0; i<N; i++){
		for(int j=i+1; j<N; j++){
			area[i][j] = max(1, abs(xs[i]-xs[j]))*max(1, abs(ys[i]-ys[j]));
			bs[i][j] = 0;
			for(int k=0; k<N; k++){
				if( (xs[i]-xs[k])*(xs[k]-xs[j]) >= 0 && (ys[i]-ys[k])*(ys[k]-ys[j])>=0){
					bs[i][j] |= (1<<k);
				}
			}
		}
	}

	for(int bit=0; bit<(1<<N); bit++){
		for(int i=0; i<N; i++){
			for(int j=i+1; j<N; j++){
				int nbit = bit | bs[i][j];
				dp[nbit] = min(dp[nbit], dp[bit] + area[i][j]);
			}
		}
	}

	return dp[(1<<N)-1];
}

int main(){
	for(;init();){
		printf("%d\n", solve());
	}

	return 0;
}