ZOJ-3537

題目大意：給你一個n (n<=300) 邊形，給出它所有的頂點坐標，讓你把它劃分成n-2個三角形的花費最小值，頂點 a 和 b 相連的花費為

abs(a.x+b.x)*abs(a.y+b.y)。 如果是凹多邊形輸出無解。

?

思路：先跑個凸包判斷是不是凸多邊形，跑完之后點的順序是逆時針的，我們考慮區間dp，dp[ i ][ j ]表示，從頂點 i 沿多邊形的邊逆時針跑到

頂點 j 所形成的折線和 直線i->j，所圍成的多邊形分割成小三角形所需要的花費。

狀態轉移方程： dp[ i ][ j ]=min(dp[ i ][ j ] , dp[ i ][ k ]+dp[ k ][ j ]+cost[ i ][ k ]+cost[ k ][ j ]); 如果j-i<=2 顯然花費為0，所以答案微dp[ 0 ][ n-1]。

#include<bits/stdc++.h>
using namespace std;
const int N=305;
const int inf=0x3f3f3f3f;
int n,tot,dp[N][N],cost[N][N],mod;
struct point
{
    int x,y;
    point(int _x=0,int _y=0){x=_x; y=_y;}
    point operator -(const point &rhs)const
    {
        return point(x-rhs.x,y-rhs.y);
    }
}p[N],cp[N];
typedef point vec;
int cross(const vec &a,const vec &b)
{
    return (a.x*b.y)-(a.y*b.x);
}
int dis(point a,point b)
{
    return (a.x-b.x)*(a.x-b.x)+(a.y-b.y)*(a.y-b.y);
}
bool cmp(const point &a,const point &b)
{
    int z=cross(a-p[0],b-p[0]);
    if(z>0||(z==0 && dis(p[0],a)<dis(p[0],b)))
        return 1;
    else return 0;
}
void get_cp()
{
    int k=0; tot=0;
    for(int i=0;i<n;i++)
        if(p[i].y<p[k].y || p[i].y==p[k].y && p[i].x<p[k].x) k=i;
    swap(p[0],p[k]);
    sort(p+1,p+n,cmp);
    tot=2,cp[0]=p[0];cp[1]=p[1];
    for(int i=2;i<n;i++)
    {
        while(tot>1 && cross(cp[tot-2]-cp[tot-1],p[i]-cp[tot-1])>0) tot--;
        cp[tot++]=p[i];
    }
}
void init()
{
    memset(dp,-1,sizeof(dp));
    memset(cost,0,sizeof(cost));
}
int solve(int l,int r)
{
    if(dp[l][r]!=-1) return dp[l][r];
    if(r-l<=2) return 0;
    dp[l][r]=inf;
    for(int k=l+1;k<=r-1;k++)
        dp[l][r]=min(solve(l,k)+solve(k,r)+cost[l][k]+cost[k][r],dp[l][r]);
    return dp[l][r];
}
int main()
{
    while(scanf("%d%d",&n,&mod)!=EOF)
    {
        for(int i=0;i<n;i++) scanf("%d%d",&p[i].x,&p[i].y);
        get_cp();
        if(tot<n)
        {
            puts("I can't cut.");
            continue;
        }
        init();
        for(int i=0;i<n;i++)
            for(int j=i+2;j<n;j++)
                cost[i][j]=cost[j][i]=abs(cp[i].x+cp[j].x)*abs(cp[i].y+cp[j].y)%mod;

        printf("%d\n",solve(0,n-1));
    }

    return 0;
}

?