zoj3537[最优三角剖分]

链接:zoj3537[最优三角剖分]

题解

  • 先判个凸多边形,然后最优三角剖分,DP[i][j]=min(DP[i][j,DP[i][k]+DP[k][j]+cst[i][k]+cst[k][j])
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    13
    14
    15
    16
    17
    18
    19
    20
    21
    22
    23
    24
    25
    26
    27
    28
    29
    30
    31
    32
    33
    34
    35
    36
    37
    38
    39
    40
    41
    42
    43
    44
    45
    46
    47
    48
    49
    50
    51
    52
    53
    54
    55
    #include<iostream>
    #include<cstdio>
    #include<cmath>
    #include<cstdlib>
    #include<cstring>
    #include<cmath>
    #include<algorithm>
    #define rint register int
    #define rep(i,x,y) for(rint i=x;i<=y;++i)
    #define repd(i,x,y) for(rint i=x;i>=y;--i)
    #define ll long long
    using namespace std;
    const int N=407;
    const ll inf=0x3f3f3f3f;
    int n,p,cnt;
    ll dp[N][N],x[N],y[N],res[N],id[N],cst[N][N];
    template <typename T>inline void read(T &x){
    x=0;char c;int sign=1;
    do{c=getchar(); if(c=='-')sign=-1;}while(c<'0'||c>'9');
    do{x=x*10+c-'0'; c=getchar();}while(c>='0'&&c<='9');
    x*=sign;
    }
    inline ll cul(int a,int b,int c){return abs(x[a]+x[b])*abs(y[a]+y[b])%p+abs(x[c]+x[b])*abs(y[c]+y[b])%p;}
    inline int cmp(int a,int b){return y[a]==y[b]?x[a]<x[b]:y[a]<y[b];}
    inline int crp(int x1,int y1,int x2,int y2){return x1*y2-x2*y1;}
    inline int init(){
    cnt=0;
    rep(i,1,n)read(x[i]),read(y[i]),id[i]=i;sort(id+1,id+n+1,cmp);
    rep(i,1,n){
    while(cnt>1&&crp(x[res[cnt]]-x[res[cnt-1]],y[res[cnt]]-y[res[cnt-1]],x[id[i]]-x[res[cnt-1]],y[id[i]]-y[res[cnt-1]])<=0)--cnt;
    res[++cnt]=id[i];
    }
    int tmp=cnt;
    repd(i,n-1,1){
    while(cnt>tmp&&crp(x[res[cnt]]-x[res[cnt-1]],y[res[cnt]]-y[res[cnt-1]],x[id[i]]-x[res[cnt-1]],y[id[i]]-y[res[cnt-1]])<=0)--cnt;
    res[++cnt]=id[i];
    }
    return cnt==n+1;
    }
    inline void solve(){
    memset(dp,0x3f,sizeof(dp));
    memset(cst,0,sizeof(cst));
    rep(i,1,n-1)dp[i][i+1]=0;
    rep(i,1,n)rep(j,i+2,n)
    cst[i][j]=cst[j][i]=abs(x[res[i]]+x[res[j]])*abs(y[res[i]]+y[res[j]])%p;
    repd(i,n-2,1)rep(j,i+2,n)rep(k,i+1,j-1)dp[i][j]=min(dp[i][j],dp[i][k]+dp[k][j]+cst[i][k]+cst[k][j]);
    }
    int main(){
    while(~scanf("%d%d",&n,&p)){
    if(!init()){puts("I can't cut.");continue;}
    solve();
    printf("%d\n",dp[1][n]);
    }
    return 0;
    }