题意：一块多边形先判凸凹，凸则三角剖分
三角剖分模型和最优矩阵链乘模型几乎相同，都是对区间的DP，只不过最优矩阵链乘的最后次乘法决定了决策顺序，三角剖分没天然的顺序，，所以要人为加上顺序
凸包用了卷包裹法
//Accepted 3537 C++ 0 1004#include<cstdio>#include<cstring>#include<iostream>#include<algorithm>#include <cmath>#include <queue>using namespace std;int mod,n;const int maxn=305;struct node{int x,y;}e[maxn],res[maxn];bool cmp(node a,node b){if(a.x==b.x)return a.y<b.y;return a.x<b.x;}int cross(node a,node b,node c)//向量积{return (a.x-c.x)*(b.y-c.y)-(b.x-c.x)*(a.y-c.y);}int convex(int n)//求凸包上的点{sort(e,e+n,cmp);int m=0,i,k;//求得下凸包，逆时针//已知凸包点m个，如果新加入点为i，则向量(m-2,i)必定要在(m-2,m-1)的逆时针方向才符合凸包的性质 //若不成立，则m-1点不在凸包上。for(i=0;i<n;i++){while(m>1&&cross(res[m-1],e[i],res[m-2])<=0)m–;res[m++]=e[i];}k=m;//求得上凸包for(i=n-2;i>=0;i–){while(m>k&&cross(res[m-1],e[i],res[m-2])<=0)m–;res[m++]=e[i];}if(n>1)m–;//起始点重复。return m;}int w[maxn][maxn];int dp[maxn][maxn];int calc(int u,int v){return abs((res[u].x+res[v].x)*(res[u].y+res[v].y))%mod;}int morize(int l,int r){int &ans=dp[l][r];if(ans>=0) return ans;if(l+1==r) return ans=0;for(int k=l+1;k<r;k++){ans = k==l+1? morize(l,k)+morize(k,r)+w[l][k]+w[k][r]: min(ans,morize(l,k)+morize(k,r)+w[l][k]+w[k][r]);}return ans;}void ini(){memset(dp,0,sizeof(dp));}int main(){while(~scanf("%d%d",&n,&mod)){ini();for(int i=0;i<n;i++)scanf("%d%d",&e[i].x,&e[i].y);int cnt=convex(n);if(cnt<n){puts("I can't cut.");continue;}for(int i=0;i<cnt;i++)for(int j=i+2;j <cnt;j++)w[i][j] = w[j][i]= calc(i,j);for(int l=1;l<cnt;l++)for(int p=0;p+l<cnt;p++)for(int k=p+1;k<p+l;k++)dp[p][p+l]= k==p+1? dp[p][k]+dp[k][p+l]+w[p][k]+w[k][p+l] : min(dp[p][p+l],dp[p][k]+dp[k][p+l]+w[p][k]+w[k][p+l]);printf("%d\n",dp[0][cnt-1]);}return 0;}
只有不断找寻机会的人才会及时把握机会。
