首页 > 其他 > 详细

凸多边形的划分

时间:2021-05-20 09:58:31      阅读:21      评论:0      收藏:0      [点我收藏+]
#include <bits/stdc++.h>
using namespace std;
const int N = 55, M = 35;
int n;
int w[N];
int dp[N][N][M];
void add(int a[],int b[]){
    int t=0;
    for(int i=0;i<M;i++){
        t+=a[i]+b[i];
        a[i]=t%10;
        t/=10;
    }
}
void mul(int a[],int b){
    long long t=0;
    for(int i=0;i<M;i++){
        t+=1ll*a[i]*b;
        a[i]=t%10;
        t/=10;
    }
}
int cmp(int a[],int b[]){
    for(int i=M-1;i>=0;i--){
        if(a[i]>b[i])return 1;
        else if(a[i]<b[i])return -1;
    }
    return 0;
}
void print(int a[]){
    int k=M-1;
    while(k&&!a[k])k--;
    while(k>=0)cout<<a[k--];
}
int main()
{
    ios::sync_with_stdio(false);
    cin>>n;
    for(int i=1;i<=n;i++)cin>>w[i];
    int temp[M];
    for(int len=3;len<=n;len++){
        for(int j=1;j+len<=n+1;j++){
            int ends=j+len-1;
            dp[j][ends][M-1]=1;
            for(int i=j+1;i<ends;i++){
                memset(temp,0,sizeof temp);
                temp[0]=1;
                mul(temp,w[j]);
                mul(temp,w[i]);
                mul(temp,w[ends]);
                add(temp,dp[j][i]);
                add(temp,dp[i][ends]);
                if(cmp(dp[j][ends],temp)>0)
                memcpy(dp[j][ends],temp,sizeof temp);
            }
        }
    }
    print(dp[1][n]);
    return 0;
}

  

凸多边形的划分

原文:https://www.cnblogs.com/qq1415584788/p/14788449.html

(0)
(0)
   
举报
评论 一句话评论(0
关于我们 - 联系我们 - 留言反馈 - 联系我们:wmxa8@hotmail.com
© 2014 bubuko.com 版权所有
打开技术之扣,分享程序人生!