ZOJ 3537 Cake （区间DP，三角形剖分）

题意：

　　给出平面直角坐标系上的n个点的坐标，表示一个多边形蛋糕，先判断是否是凸多边形，若否，输出"I can't cut."。若是，则对这个蛋糕进行3角形剖分，切n-3次变成n-2份三角形蛋糕给小伙伴吃，但是每切一次需要一个费用，公式是：cost[i][j] = |x_i + x_j| * |y_i + y_j| % p 表示在两点i和j之间切一刀的费用。问最少费用是多少？

思路：

　　判断是否凸多边形需要用到求凸包的Andrew算法，时间复杂度为O(nlogn)，然后判断凸包内的点数是否为n就行了。（大白书p271）

　　求最小费用需要用到分治的一些思想，当然主要还是dp。

　　如下图的凸多边形（图来自这里），如果点1和点n还差1个点就成为三角形了，我们可以枚举这个点k，切两刀，取出K0（不能再切），变成K1和K2两块，以刚切的1->k和k->n这两条边为基边，继续分治切下去，直到剩下1个三角形为止。那么以edge[i][j]为基边来切开这个子凸多边形的费用是dp[i][j]=max(dp[i][j], dp[i][k]+dp[i][k]+cost[i][k]+cost[k][j])，所有点对的cost可以先求出来。注意在计算dp[i][j]时，dp[i][k]和dp[k][j]必须先求出来。

 //#include <bits/stdc++.h>

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cmath>

 #include <map>

 #include <deque>

 #include <algorithm>

 #include <vector>

 #include <iostream>

 #define pii pair<int,int>

 #define max(x,y) ((x)>(y)?(x):(y))

 #define min(x,y) ((x)<(y)?(x):(y))

 #define abs(x) ((x)<0?-(x):(x))

 #define INF 0x3f3f3f3f

 #define LL  long long

 using namespace std;

 const double PI  = acos(-1.0);

 const int N=;

 struct node

 {

     int x,y;

     node(){};

     node(int x,int y):x(x),y(y){};

 }Po[N], path[N];

 int n, p, c[N][N], dp[N][N];

 inline int cmp(node a,node b)

 {

     if(a.x==b.x)    return a.y<b.y;

     return a.x<b.x;

 }

 inline int cross(node A,node p1,node p2)    //叉积,A是新来的点。若A在p1->p2左边，则结果为正。

 {

     return (p1.x-A.x)*(p2.y-A.y) - (p2.x-A.x)*(p1.y-A.y);

 }

 int get_cost(node a,node b){return abs(a.x+b.x)*abs(a.y+b.y)%p;}    //在a和b之间切开的费用

 int ConvexHull(node *u,int n,node *path)    //求凸包，返回凸包中的点数

 {

     sort(u,u+n,cmp);            //先按x再按y排序

     int top=;

     for(int i=; i<n; i++)      //下凸包:从左到右

     {

         while(top> && cross(u[i],path[top-],path[top-])<= )  top--; //小于0，在右边

         path[top++]=u[i];

     }

     int k=top;

     for(int i=n-; i>=; i--)   //上凸包：从右到左

     {

         while(top>k && cross(u[i],path[top-],path[top-])<= )  top--;

         path[top++]=u[i];

     }

     if(n>) top--;  //起点是重复了的，要去掉

     return top;

 }

 int cal()

 {

     if(n==)    return ;           //3点则0费用

     memset(c,,sizeof(c));

     for(int i=; i<n; i++)          //任意两点间连一条边的费用c

         for(int j=i+; j<n; j++)

             c[i][j]=c[j][i]=get_cost( path[i], path[j] );

     for(int i=; i<n; i++)

     {

         for (int j=; j<n; j++) dp[i][j]=INF;

         dp[i][i+] = ;         //相邻两个点不能连线，可视为费用为0.

     }

     for(int j=; j<n; j++)          //升序

     {

         for(int i=j-; i>=; i--)   //降序

         {

             for(int k=i+; k<j; k++)    //枚举三角形顶点

                 dp[i][j]=min(dp[i][j], dp[i][k]+dp[k][j]+c[i][k]+c[k][j]);

         }

     }

     return dp[][n-];

 }

 int main()

 {

     //freopen("input.txt", "r", stdin);

     while(~scanf("%d%d",&n,&p))

     {

         for(int i=; i<n; i++)    scanf("%d%d",&Po[i].x,&Po[i].y);

         if(ConvexHull(Po,n,path)<n)  puts("I can't cut.");

         else                         printf("%d\n", cal());

     }

     return ;

 }

AC代码

巴特西

ZOJ 3537 Cake （区间DP，三角形剖分）

最新文章

热门文章