zoj 3537 cake 切蛋糕 區間DP+凸包+遞歸 最優三角形剖分

題意：給出一些點表示多邊形蛋糕的定點的位置（如果蛋糕是凹多邊形就不能切），切蛋糕時每次隻能在頂點和頂點間切，每一次切蛋糕都有相應的代價，給出代價的公式，問把蛋糕切成多個三角形的最小代價是多少

由于有可能是凹多邊形，是以得先判斷凸性，直接求凸包，然後判斷凸包頂點和所給點的大小，然後再解決最小代價。

最小代價，其實就是最優三角形剖分，小白上有提到。

我用去點的思路yy了好幾天，越想越複雜，于是網上看了一下，發現原來是按邊操作orz，改完後終于過了，好感動TAT.

我們用dp[i][j]表示從i點到j點所構成的多邊形的最優三角剖分，我們以j-i邊為三角形的一邊，那麼三角形的另一個頂點就在i+1到j-1中，這就是區間dp了。當然之前得預處理下各個切刀的代價。

我這邊用的是遞歸，如果想看遞推可以去zeroclock大神的部落格看看，他的圖解很精彩。。

代碼：

/*
*  Author:      illuz <iilluzen[at]gmail.com>
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        zoj3537.cpp
*  Create Date: 2013-12-04 16:35:27
*  Descripton:  convex hull + intervel dp 
*/

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

#define sqr(a) ((a) * (a))
#define dis(a, b) sqrt(sqr(a.x - b.x) + sqr(a.y - b.y))

const int MAXN = 305;
const int INF = 0x3c3c3c3c;
const double PI = acos(-1.0);

struct Point {
	double x;
	double y;
	Point(double a = 0, double b = 0) : x(a), y(b) {}
	friend bool operator < (const Point &l, const Point &r) {
		return l.y < r.y || (l.y == r.y && l.x < r.x);
	}
} p[MAXN], ch[MAXN * 2], tmp[MAXN];
// p, point   ch, convex hull

int f[MAXN][MAXN], c[MAXN][MAXN];		// rec and cast
int P;

double mult(const Point &a, const Point &b, const Point &o) {
	return (a.x - o.x) * (b.y - o.y) >= (b.x - o.x) * (a.y - o.y);
}

double Graham(Point p[], int n, Point res[]) {
	int top = 1;
	sort(p, p + n);
	if (n == 0) return 0;
	res[0] = p[0];
	if (n == 1) return 0;
	res[1] = p[1];
	if (n == 2) return dis(p[0], p[1]) * 2;
	res[2] = p[2];
	for (int i = 2; i < n; i++) {
		while (top && (mult(p[i], res[top], res[top - 1])))
			top--;
		res[++top] = p[i];
	}
	int len = top;
	res[++top] = p[n - 2];
	for (int i = n - 3; i >= 0; i--) {
		while (top != len && (mult(p[i], res[top], res[top - 1])))
			top--;
		res[++top] = p[i];
	}
	return top;
}

int calc(int i, int j) {
	return (abs((int)ch[i].x + (int)ch[j].x) * abs((int)ch[i].y + (int)ch[j].y)) % P;
}

int dp(int l, int r) {
	if (f[l][r]) return f[l][r];
	if (r - l <= 2) return 0;
	int ans = INF;
	for (int i = l + 1; i < r; i++) {
		ans = min(ans, dp(l, i) + dp(i, r) + c[l][i] + c[i][r]);
	}
	return f[l][r] = ans;
}

int main() {
	int n;
	while (~scanf("%d%d", &n, &P)) {
		for (int i = 0; i < n; i++)
			scanf("%lf%lf", &p[i].x, &p[i].y);
		if (n <= 3) {
			puts("0");
			continue;
		}
		if (Graham(p, n, ch) < n)
			puts("I can't cut.");
		else {
			memset(f, 0, sizeof(f));
			for (int i = 0; i < n; i++)
				for (int j = i + 2; j < n; j++)
					c[i][j] = c[j][i] = calc(i, j);

			printf("%d\n", dp(0, n - 1));
		}
	}
	return 0;
}