题意:给定n个点的坐标,先问这些点是否能组成一个凸包,如果是凸包,问用不相交的线来切这个凸包使得凸包只由三角形组成,根据costi, j ,问最少的切割费用。
思路:经典的区间DP
dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]+cost[i][k]+cost[k][j])
dp[i][j]表示为以i为起点,j为终点的凸包内部被切割的最小费用
另外,这里需要用Graham 求是否为凸包,直接上模板,不能用旋向法是因为输入点并不一定是顺时针或逆时针
Code:
#include <iostream> #include <cstdio> #include <algorithm> #include <cmath> #include <cstring> #include <string> #include <iomanip> #include <queue> #include <vector> #include <set> #include <map> typedef long long LL; #define inf 0x3f3f3f3f #define P system("pause") using namespace std; #define M 305 struct node { int x,y; }p[M]; int cross(node a,node b,node c) { return ((b.x-a.x)*(c.y-a.y)-(b.y-a.y)*(c.x-a.x)); } //判断点l是否比点r更下更左 bool isBottomLeft(node const&l,node const&r){ if ( l.y != r.y ) return l.y < r.y; return l.x < r.x; } //为Graham排序做准备 node* pOrigin; bool is4Graham(node const&l,node const&r){ int t = cross(*pOrigin,l,r); if ( t ) return t > 0; return (l.x-pOrigin->x)*(l.x-pOrigin->x)<(r.x-pOrigin->x)*(r.x-pOrigin->x); } //Graham求严格凸包 int Graham(node p[],int n){ if ( 1 == n ) return 1; //求最下最左点 node* t = min_element(p,p+n,isBottomLeft); //与0点交换位置 node ptmp(*t); *t = p[0]; p[0] = ptmp; //相对于0点排序 pOrigin = p; sort(p+1,p+n,is4Graham); //建栈循环 int top = 2; for(int i=2;i<n;++i){ while( top>1 && cross(p[top-2],p[top-1],p[i])<=0 ) --top; p[top++] = p[i]; } if( top>=3 && 0==cross(p[0],p[top-1],p[top-2]) ) --top; return top; } int dp[M][M],cost[M][M]; int main() { int n,m; int i,j,k; while(scanf("%d%d",&n,&m)!=EOF) { for(i=0;i<n;i++) scanf("%d%d",&p[i].x,&p[i].y); int tot=Graham(p,n); if(tot<n) { puts("I can't cut."); continue; } memset(dp,0,sizeof(dp)); memset(cost,0,sizeof(cost)); for(i=0;i<n;i++) for(j=i+2;j<n;j++) cost[i][j]=(abs(p[i].x+p[j].x)*abs(p[i].y+p[j].y))%m; for(i=n;i>=0;i--) { for(j=i+2;j<n;j++) { int tem=inf; for(k=i+1;k<=j-1;k++) { tem=min(tem,dp[i][k]+dp[k][j]+cost[i][k]+cost[k][j]); } dp[i][j]=tem; } } printf("%d\n",dp[0][n-1]); } return 0; }