SRM 386 500pt: PolygonCover

TopCoder

問題概要

凸多角形(頂点数N<=15)が与えられる。この頂点を複数個選んでできる多角形を集めて頂点を被覆したい。面積の和を最小化する問題。ただし面積が重複している部分は複数回カウントする。

考えたこと

  • サイズからしてビットDP？
  • 多角形で覆うとか言ってるけど三角形に分割できるので三角形だと思っていい。
  • 更新するのは三角形全部作ればいい。
  • 三角形の数の大さがちょっと気になる。電卓でcombination(15,3) * 2^15を計算。ちょっと大きいけどギリギリ間に合いそう。
  • この計算、実は全部整数でできるので少し大きいくらいなら間に合うだろう。
  • メモ化再帰で書こうとしたけど上手くかけなかった。仕方ないので配るDPをループで書く。
    • スーパーセットに配るタイプのビットDPなのでビットの回し方は単純。
  • 一発コンパイルで無事通った。
  • おまけ：これ結局メモ化再帰で自然に書く方法はあるんだろうか？

practiceで通ったコード

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

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

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

int dp[1<<MAX_N];

struct PolygonCover {

	double getArea(vector <int> x, vector <int> y) {
		const int N = x.size();

		//初期化
		fill(dp, dp+(1<<N), INF);

		//基底
		dp[0] = 0;

		//ビットDP
		for(int bit=0; bit<(1<<N); bit++){
			//新たに三角形を作ってかぶせる
			for(int i=0; i<N; i++){
				for(int j=i+1; j<N; j++){
					for(int k=j+1; k<N; k++){
						int next_bit = bit | (1<<i) | (1<<j) | (1<<k);
						int area = dp[bit] + getTriangleArea(x[i], y[i], x[j], y[j], x[k], y[k]);
						dp[next_bit] = min(dp[next_bit], area);
					}
				}
			}
		}

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

	//三角形の面積の2倍の値を返す
	inline int getTriangleArea(int x1, int y1, int x2, int y2, int x3, int y3){
		return abs((y2-y3)*(x1-x3) - (x2-x3)*(y1-y3));
	}
};