ZOJ 3537 区间dp

蔚落 2022-08-18 11:49 185阅读 0赞

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

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

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

#include <stdio.h>
    #include <string.h>
    #include <math.h>
    #include <algorithm>
    using namespace std;
    #define MAX 1000
    #define INF 100000000
    #define min(a,b) ((a)<(b)?(a):(b))
    
    
    struct point
    {
        int x,y;
    }p[MAX];
    
    int cost[MAX][MAX],n,m;
    int dp[MAX][MAX];
    
    
    int abs(int x) {
    
    	return x < 0 ? -x : x;
    }
    point save[400],temp[400];
    
    int xmult(point p1,point p2,point p0)
    {
        return (p1.x-p0.x)*(p2.y-p0.y)-(p2.x-p0.x)*(p1.y-p0.y);
    }
    bool cmp(const point& a,const point &b)
    {
        if(a.y == b.y)return a.x < b.x;
    	return a.y < b.y;
    }
    int Graham(point *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 Count(point a,point b) 
    {
    	return (abs(a.x + b.x) * abs(a.y+b.y)) % m;
    }
    
    
    int main()
    {
    	int i,j,k,r,u;
    	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) 
            {
                printf("I can't cut.\n");
                continue;
            }
    
            memset(cost,0,sizeof(cost));
            for (i = 0; i < n; ++i)
                for (j = i + 2; j < n; ++j)
                    cost[i][j] = cost[j][i] = Count(save[i],save[j]);
    
    
            for (i = 0; i < n; ++i) 
            {
                for (j = 0; j < n; ++j)
                {
                    dp[i][j] = INF;
                }
                dp[i][(i+1)%n] = 0;
            }
            for (i = n - 3; i >= 0; --i)	//注意这三个for循环的顺序
                for (j = i + 2; j < n; ++j) //因为要保证在算dp[i][j]时dp[i][k]和dp[k][j]时已经计算，所以i为逆序，j要升序
                    for (k = i + 1; k <= j - 1; ++k)
                        dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]+cost[i][k]+cost[k][j]);
    
    
            printf("%d\n",dp[0][n-1]);
    	}
    }
    
    
    /*
    3 3
    0 0
    1 1
    0 2
    
    4 100
    0 0
    1 0
    0 1
    1 1
    
    4 100
    0 0
    3 0
    0 3
    1 1
    */