深圳彩票网站建设,企业网站建设调研报告,如何搭建门户网站,wordpress彩色标签云Cake 题意
给定平面坐标上的 n n n 个点#xff0c;如果是凸多边形的话#xff0c;就用最少的花费把这个多边形剖分成若干个三角形#xff0c;剖分的线段端点只能是原多边形的顶点#xff0c;一条线段的花费为#xff1a; ∣ x i x j ∣ ∣ y i y j ∣ m o d p |x_i…Cake 题意
给定平面坐标上的 n n n 个点如果是凸多边形的话就用最少的花费把这个多边形剖分成若干个三角形剖分的线段端点只能是原多边形的顶点一条线段的花费为 ∣ x i x j ∣ × ∣ y i y j ∣ m o d p |x_i x_j| \times |y _i y_j| mod p ∣xixj∣×∣yiyj∣modp
思路
首先我们使用 A n d r e w Andrew Andrew 算法判断一下是否为凸包。对于当前的顶点 [ 0 , n − 1 ] [0, n - 1] [0,n−1]我们先看一条边 0 ↔ n − 1 0 \lrarr n - 1 0↔n−1这条边肯定属于某个三角形我们肯定要有一条线的端点之一是 0 0 0另外一条线的端点之一是 n − 1 n - 1 n−1并且这两条线有一个公共端点 k ( 1 ≤ k ≤ n − 2 ) k(1 \leq k \leq n - 2) k(1≤k≤n−2)因为只有这样才能将这条边剖分成属于某个三角形而那两条线段就是三角形的两条边第三条边就是 0 ↔ n − 1 0 \lrarr n - 1 0↔n−1
那么这两条线就将我们的 [ 0 , n − 1 ] [0, n - 1] [0,n−1] 区间的端点分成了两个部分 [ 0 , k ] [0, k] [0,k] 和 [ k 1 , n − 1 ] [k 1, n - 1] [k1,n−1]这是两个子状态我们可以使用 d p [ l ] [ r ] dp[l][r] dp[l][r] 表示区间 [ l , r ] [l,r] [l,r] 的三角剖分的最小花费
那么转移就可以枚举区间的分裂点 k k k d p [ l ] [ k ] m i n l 1 ≤ k ≤ r − 1 ( d p [ l ] [ k ] d p [ k 1 ] [ r ] c o s t ( l , k ) c o s t ( k , r ) ) dp[l][k] min_{l 1 \leq k \leq r - 1} (dp[l][k] dp[k 1][r] cost(l, k) cost(k, r)) dp[l][k]minl1≤k≤r−1(dp[l][k]dp[k1][r]cost(l,k)cost(k,r)) c o s t ( l , k ) cost(l,k) cost(l,k) 表示连接 l l l 和 k k k 的花费
注意如果 l 1 ≤ r l 1 \leq r l1≤r 时 c o s t ( l , r ) 0 cost(l, r) 0 cost(l,r)0因为原本的多边形上已经有了这条边不用而外花费去切割
跑区间 D P DP DP 的时候我们从长度为 3 3 3 的区间开始长度小于等于 2 2 2 的区间花费都为 0 0 0都不用切割
时间复杂度 O ( n 3 ) O(n^3) O(n3)
#includebits/stdc.h
#define fore(i,l,r) for(int i(int)(l);i(int)(r);i)
#define fi first
#define se second
#define endl \n
#define ull unsigned long long
#define ALL(v) v.begin(), v.end()
#define Debug(x, ed) std::cerr #x x ed;const int INF0x3f3f3f3f;
const long long INFLL1e18;typedef long long ll;int mod;struct Point{int x,y;Point(int xx0,int yy0){xxx,yyy;}Point operator (Point B){ //向量 return Point(xB.x,yB.y);}Point operator - (Point B){ //向量 -return Point(x-B.x,y-B.y);}Point operator * (int k){ //向量等比例放大return Point(k*x,k*y);}bool operator (Point B){ //unique 用到return x-B.x 0 y-B.y 0;}bool operator (Point B){return x-B.x 0 || (x-B.x 0 y-B.y 0);}
};int Cross(Point A,Point B){return A.x*B.y - A.y*B.x;
}int Convex_hull(Point* p,int n,Point* ch){ //ch[]储存凸包顶点n std::unique(p,pn) - p; //去重std::sort(p,pn); //排序int v 0;/* 求下凸包 */fore(i,0,n){while(v1 Cross(ch[v-1]-ch[v-2],p[i]-ch[v-2]) 0)--v;ch[v] p[i];}int j v;/* 求上凸包 */for(int in-2;i0;--i){while(vj Cross(ch[v-1]-ch[v-2],p[i]-ch[v-2]) 0)--v;ch[v] p[i];}if(n1) --v; //p[0]被加入了两次return v; //返回凸包顶点数
}Point p[500];
Point ch[500];int main(){std::ios::sync_with_stdio(false);std::cin.tie(nullptr);std::cout.tie(nullptr);int n;while(std::cin n mod){fore(i, 0, n) std::cin p[i].x p[i].y;if(Convex_hull(p, n, ch) n){ //不是凸包std::cout I cant cut.\n;continue;}if(n 3){std::cout 0\n;continue;}std::vectorstd::vectorint dp(n 5, std::vectorint(n 5, INF));std::vectorstd::vectorint dis(n 5, std::vectorint(n 5, 0)); //连接两个顶点的costauto cal [](int i, int j) { //计算costreturn std::abs(ch[i].x ch[j].x) * std::abs(ch[i].y ch[j].y) % mod;};fore(i, 0, n)fore(j, i 2, n)dis[i][j] dis[j][i] cal(i, j); //预计算costfore(i, 0, n) dp[i][i 1] 0;fore(len, 3, n 1)fore(L, 0, n - len 1){int R L len - 1;fore(k, L 1, R)dp[L][R] std::min(dp[L][R], dp[L][k] dp[k][R] dis[L][k] dis[k][R]);}std::cout dp[0][n - 1] endl;}return 0;
}
