ZOJ - 3537 Cake （凸包+經典區間dp）

題目連結：點選這裡

題目大意：

給定 n n n 個點的坐标，如果這 n n n 個點能構成凸包，再用不相交的線來切這個凸包使得凸包隻由三角形組成，切割代價是 c o s t ( i , j ) = ∣ x i + x j ∣ ∗ ∣ y i + y j ∣ cost(i, j) = |xi + xj| * |yi + yj| % p cost(i,j)=∣xi+xj∣∗∣yi+yj∣ ，求最少的切割費用。

題目分析：

先用把點排個序跑個凸包，如果是凸包再跑一下三角形劃分的區間 d p dp dp ，其轉移方程為： d p [ i ] [ j ] = m i n ( d p [ i ] [ j ] , d p [ i ] [ k ] + d p [ k ] [ j ] + c o s t [ i ] [ k ] + c o s t [ k ] [ j ] ) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+cost[i][k]+cost[k][j]) dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+cost[i][k]+cost[k][j]) ，正常 O ( n 3 ) O(n^3) O(n3) 轉移即可

具體細節見代碼：

//#pragma GCC optimize(2)
//#pragma GCC optimize("Ofast","inline","-ffast-math")
//#pragma GCC target("avx,sse2,sse3,sse4,mmx")
#include<iostream>
#include<cstdio>
#include<iomanip>
#include<cstring>
#include<algorithm>
#include<cmath>
#include<vector>
#include<set>
#include<map>
#include<stack>
#include<queue>
#define ll long long
#define inf 0x3f3f3f3f
//#define int  ll
#define endl '\n'
#define IOS ios::sync_with_stdio(0); cin.tie(0); cout.tie(0)
using namespace std;
int read()
{
	int res = 0,flag = 1;
	char ch = getchar();
	while(ch<'0' || ch>'9')
	{
		if(ch == '-') flag = -1;
		ch = getchar();
	}
	while(ch>='0' && ch<='9')
	{
		res = (res<<3)+(res<<1)+(ch^48);//res*10+ch-'0';
		ch = getchar();
	}
	return res*flag;
}
const int maxn = 5e2+5;
const int mod = 1e9+7;
const double pi = acos(-1);
const double eps = 1e-8;
struct Point{
	int x,y;
	bool operator<(const Point&b) const {
		return x==b.x ? y<b.y : x<b.x;
	}
	Point operator-(const Point&b)const {
		return {x-b.x,y-b.y};
	}
}nod[maxn],st[maxn];
int n,p,c[maxn][maxn],dp[maxn][maxn];
double get_cross(Point a,Point b)
{
	return a.x*b.y-b.x*a.y;
}
int Convex_Hull() // 凸包，傳回凸包點數 
{
	sort(nod+1,nod+n+1);
	int top = -1;
	st[++top] = nod[1];
	st[++top] = nod[2];
	for(int i = 3;i <= n;i++)
	{
		while(top>0 && get_cross(st[top]-st[top-1],nod[i]-st[top-1])<=0) top--;
		st[++top] = nod[i];
	}
	int up = top;
	for(int i = n-1;i;i--)
	{
		while(top>up && get_cross(st[top]-st[top-1],nod[i]-st[top-1])<=0) top--;
		st[++top] = nod[i];
	}
	return top;
}
int cost(Point a,Point b)
{
	return (abs(a.x+b.x)*abs(a.y+b.y))%p;
} 
int main() 
{
	while(cin>>n>>p)
	{
		memset(dp,0x3f,sizeof(dp));
		memset(c,0,sizeof(c));
		for(int i = 1;i <= n;i++) dp[i][i+1] = 0;
		for(int i = 1;i <= n;i++) nod[i].x = read(),nod[i].y = read();
//		cout<<Convex_Hull()<<endl;
		if(Convex_Hull() < n)
		{
			puts("I can't cut.");
			continue;
		}
		for(int i = 1;i <= n;i++)
			for(int j = i+2;j <= n;j++) c[i][j] = c[j][i] = cost(st[i],st[j]);
		for(int l = 2;l <= n;l++)
			for(int i = 1,j = l;j <= n;i++,j++)
				for(int k = i+1;k <= j;k++) 
				dp[i][j] = min(dp[i][j],dp[i][k]+dp[k][j]+c[i][k]+c[k][j]);
		cout<<dp[1][n]<<endl;
	}
	return 0;
}