信息学奥赛一本通 1571. 凸多边形的划分
原题链接
中等
作者:
保底不歪抽早柚
,
2021-08-17 09:44:37
,
所有人可见
,
阅读 206
/*
题目中的每条边最大为10^9,long long 和int(无取模运算)很有可能会爆掉(既有加的操作又有乘的操作),
考虑会使用高精度算法链接:https://cauz.cn/?id=131
状态表示:f[l,r]
集合:当前划分到的多边形的左端点是l,右端点是r
属性:方案费用的最小值
状态计算:
f[l,r]=min(f[l,k]+f[k,r]+wl*wk*wr)(l<k<r)
*/
#include <iostream>
#include <cstring>
#include <algorithm>
#include <vector>
#define MAXN 55
using namespace std;
typedef long long LL;
int n;
LL w[MAXN];
vector <int> f[MAXN][MAXN];
//判断是否有A<=B
int cmp(vector<int> &A,vector<int> &B)
{
if(A.size()!=B.size())
return A.size()<B.size();
for(int i=A.size()-1;i>=0;i--)
if(A[i]!=B[i])
return A[i]<B[i];
return 1;
}
//C=A+B
vector<int> add(vector<int> A,vector<int> B)
{
vector<int> C;
int t=0;//进位
for(int i=0;i<A.size()||i<B.size();i++)
{
if(i<A.size())
t+=A[i];
if(i<B.size())
t+=B[i];
C.push_back(t%10);
t/=10;
}
if(t)//看最高位是否还有进位
C.push_back(t%10);
return C;
}
//C=A*B
vector<int> mul(vector<int> A,LL b)
{
vector<int> C;
LL t=0;//进位
for(int i=0;i<A.size()||t;i++)
{
if(i<A.size())
t+=A[i]*b;
C.push_back(t%10);
t/=10;
}
while(C.size()>1&&C.back()==0)
C.pop_back();
return C;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
scanf("%lld",&w[i]);
for(int len=3;len<=n;len++)
{
for(int l=1,r;(r=(l+len-1))<=n;l++)
{
for(int k=l+1;k<r;k++)
{
//计算wl*wr*wk
vector<int> temp=mul(mul({w[l]},w[k]),w[r]);
//计算temp+f[l,k]+f[k,r]
temp=add(add(temp,f[l][k]),f[k][r]);
//取min
if(f[l][r].size()==0||cmp(temp,f[l][r])==1)
f[l][r]=temp;
}
}
}
vector <int> res=f[1][n];//逆序输出结果
for(int i=res.size()-1;i>=0;i--)
printf("%d",res[i]);
return 0;
}