凸多边形的划分(区间dp)

简介: 凸多边形的划分(区间dp)

题目传送门

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const ll N=100,INF=1LL<<63,M=500;
ll f[N][N];
int n;
ll a[N];
bool cmp(vector<ll>& a,vector<ll>& b)
{
    while(a.size()&&a.back()==0) a.pop_back();
    while(b.size()&&b.back()==0) b.pop_back();
    if(a.size()<b.size())
    {
        return false;
    }else if(a.size()>b.size())
    {
        return true;
    }else
    {
        for(int i=a.size()-1;i>=0;i--)
        {
            if(a[i]>b[i]) return 1;
            else if(a[i]<b[i]) return 0;
        }
    }
    return 0;
}
vector<ll>mul(vector<ll>A,ll b)
{
    vector<ll>C;
    ll r=0;
    for(int i=0;i<A.size();i++)
    {
        A[i]=A[i]*b;
    }
    for(int i=0;i<A.size();i++)
    {
        r=r+A[i];
        C.push_back((r)%10);
        r/=10;
    }
    while(r)
    {
        C.push_back(r%10);
        r/=10;
    }
    while(C.size()&&C.back()==0) C.pop_back();
    return C;
}
vector<ll>add(vector<ll>&A,vector<ll>&B)
{
    ll r=0;
    vector<ll>C;
    for(int i=0;i<A.size()||i<B.size();i++)
    {
        if(i<A.size()) r+=A[i];
        if(i<B.size()) r+=B[i];
        C.push_back(r%10);
        r/=10;
    }
    if(r) C.push_back(r);
    while(C.size()&&C.back()==0) C.pop_back();
    return C;
}
int main()
{
    cin>>n;
    vector<ll>f[n+1][n+1];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        f[i][j].resize(M+1);
    }
    for(int i=1;i<=n;i++)
    {
        cin>>a[i];
    }
    vector<ll>temp;
    temp.push_back(1);
    for(int len=3;len<=n;len++)
    {
        for(int i=1;i+len-1<=n;i++)
        {
            int j=i+len-1;
            f[i][j][M]=1;
            for(int k=i+1;k<j;k++)
            {
                while(temp.size()) temp.pop_back();
                temp.push_back(1);
                temp=mul(temp,a[k]);
                temp=mul(temp,a[i]);
                temp=mul(temp,a[j]);
                temp=add(temp,f[i][k]);
                temp=add(temp,f[k][j]);
                if(cmp(f[i][j],temp))
                {
                    f[i][j]=temp;
                }
               // f[i][j]=min(f[i][j],f[i][k]+f[k][j]+1LL*a[k]*a[i]*a[j]);
            }
        }
    }
    for(int i=f[1][n].size()-1;i>=0;i--)
    {
        cout<<f[1][n][i];
    }
    //cout<<f[1][n]<<endl;
}
蔡珏
+关注
目录
打赏
0
0
0
0
2
分享
相关文章
【差分数组】【图论】【分类讨论】【整除以2】3017按距离统计房屋对数目
【差分数组】【图论】【分类讨论】【整除以2】3017按距离统计房屋对数目
|
7月前
acwing 173 矩阵距离
acwing 173 矩阵距离
39 0
【深度优先搜索】【组合数学】【动态规划】1467.两个盒子中球的颜色数相同的概率
【深度优先搜索】【组合数学】【动态规划】1467.两个盒子中球的颜色数相同的概率
【图论】【分类讨论】LeetCode3017按距离统计房屋对数目
【图论】【分类讨论】LeetCode3017按距离统计房屋对数目
【差分数组】【图论】【分类讨论】【整除以2】100213按距离统计房屋对数目
【差分数组】【图论】【分类讨论】【整除以2】100213按距离统计房屋对数目
【差分数组】【图论】【分类讨论】【整除以2】100213按距离统计房屋对数目
【算法训练-动态规划 四】【二维DP问题】最大正方形、最小路径和、不同路径
【算法训练-动态规划 四】【二维DP问题】最大正方形、最小路径和、不同路径
141 0
【学会动态规划】等差数列划分(22)
【学会动态规划】等差数列划分(22)
80 0
LeetCode 周赛上分之旅 #41 结合离散化的线性 DP 问题
学习数据结构与算法的关键在于掌握问题背后的算法思维框架,你的思考越抽象,它能覆盖的问题域就越广,理解难度也更复杂。在这个专栏里,小彭与你分享每场 LeetCode 周赛的解题报告,一起体会上分之旅。
98 0
巧解“求取矩形面积划分”
巧解“求取矩形面积划分”
176 0
AI助理

你好,我是AI助理

可以解答问题、推荐解决方案等