Hatena::Grouptopcoder

hama_DU@TopCoderへの道

2011-03-27SRM300台を練習していく part2

SRM 304 PolyMove

|  SRM 304 PolyMove - hama_DU@TopCoderへの道 を含むブックマーク はてなブックマーク -  SRM 304 PolyMove - hama_DU@TopCoderへの道

http://www.topcoder.com/stat?c=problem_statement&pm=6190

自力では解けなかった。

各頂点を1だけ引き伸ばすことによる面積の増加分を全て求める。

隣り合う頂点を使うことはできないので、DPをする。更新式は以下のとおり。

dp[i] = max(dp[i-2] + i番目の頂点を伸ばすことによる増加分, dp[i-1])

注意しなければならないのは、最初の頂点と最後の頂点が隣り合っているため、

最初の頂点を使う場合と使わない場合とで二パターンのDPをする必要があること。


public class PolyMove {

	double[] inc;

	public double L(int x1, int y1, int x2, int y2) {
		return Math.hypot(Math.abs(x1 - x2),  Math.abs(y1 - y2));
	}

	public double addedArea(int[] x, int[] y) {
		int len = x.length;
		inc = new double[len];
		for (int i = 0 ; i < len ; i++) {
			int ida = ((i + len) - 1) % len;
			int idb = (i + len + 1) % len;
			inc[i] = L(x[ida], y[ida], x[idb], y[idb]);
		}

		double[] dp = new double[len];
		double[] dpx = new double[len];
		dp[0] = inc[0];
		dp[1] = Math.max(inc[0], inc[1]);
		dpx[0] = 0;
		dpx[1] = inc[1];
		for (int i = 2 ; i < len ; i++) {
			if (i == len - 1) {
				dpx[i] = Math.max(dpx[i-2] + inc[i], dpx[i-1]);
			} else {
				dp[i] = Math.max(dp[i-2] + inc[i], dp[i-1]);
				dpx[i] = Math.max(dpx[i-2] + inc[i], dpx[i-1]);
			}
		}

		return Math.max(dp[len-2], dpx[len-1]) / 2.0d;
	}

}