zoj 3537 cake 切蛋糕 区间DP+凸包+递归 最优三角形剖分

题意：给出一些点表示多边形蛋糕的定点的位置（如果蛋糕是凹多边形就不能切），切蛋糕时每次只能在顶点和顶点间切，每一次切蛋糕都有相应的代价，给出代价的公式，问把蛋糕切成多个三角形的最小代价是多少

由于有可能是凹多边形，所以得先判断凸性，直接求凸包，然后判断凸包顶点和所给点的大小，然后再解决最小代价。

最小代价，其实就是最优三角形剖分，小白上有提到。

我用去点的思路yy了好几天，越想越复杂，于是网上看了一下，发现原来是按边操作orz，改完后终于过了，好感动TAT.

我们用dp[i][j]表示从i点到j点所构成的多边形的最优三角剖分，我们以j-i边为三角形的一边，那么三角形的另一个顶点就在i+1到j-1中，这就是区间dp了。当然之前得预处理下各个切刀的代价。

我这边用的是递归，如果想看递推可以去zeroclock大神的博客看看，他的图解很精彩。。

代码：

/*
*  Author:      illuz 
  
   
*  Blog:        http://blog.csdn.net/hcbbt
*  File:        zoj3537.cpp
*  Create Date: 2013-12-04 16:35:27
*  Descripton:  convex hull + intervel dp 
*/

#include 
   
     #include 
    
      #include 
     
       #include 
      
        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; }