本文共 1153 字，大约阅读时间需要 3 分钟。

1、

2、题目大意;

给出一个多边形，将这个多边形用不相交的线段分割成一个一个的三角形，如果不能进行分割输出I can't cut.，每条分割线的代价是|x_i + x_j| * |y_i + y_j| % p，求将该多边形分割成三角形的最小代价是多少？

首先判断一下该多边形是不是凸多边形，如果是才能进行分割，如果不是直接返回I can't cut

dp[i][j]表示以i-j为基边的凸多边形分割成三角形的最小代价，

dp[i][j]=min(dp[i][k]+dp[k][j]+cost[i][k]+cost[k][j])

思路参考博客

3、AC代码：

#include
   
    #include
    
     #include
     
      using namespace std;#define N 305#define INF 0x7ffffff    int n,m;struct node{    int x;    int y;}p[N];node save[N];int dp[N][N];int cost[N][N];bool cmp(const node& a,const node &b){	if(a.y == b.y)return a.x < b.x;	return a.y < b.y;}int xmult(node p1,node p2,node p0){	return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);}int Graham(node *p,int n) {	int i;	sort(p,p + n,cmp);	save[0] = p[0];	save[1] = p[1];	int top = 1;	for(i = 0;i < n; i++){		while(top && xmult(save[top],p[i],save[top-1]) >= 0)top--;		save[++top] = p[i];	}	int mid = top;	for(i = n - 2; i >= 0; i--){		while(top>mid&&xmult(save[top],p[i],save[top-1])>=0)top--;		save[++top]=p[i];	}	return top;}int DP(int l,int r){   // printf("diaoyong %d %d\n",l,r);    if(dp[l][r])    return dp[l][r];    if(r-l<=2)    return 0;    int ans=INF;    for(int i=l+1;i
     
    
   

转载地址：http://zgddi.baihongyu.com/