题目描述
给定一个具有 N 个顶点的凸多边形,将顶点从 1 至 N 标号,每个顶点的权值都是一个正整数。
将这个凸多边形划分成 N−2 个互不相交的三角形,对于每个三角形,其三个顶点的权值相乘都可得到一个权值乘积,试求所有三角形的顶点权值乘积之和至少为多少。
输入格式
第一行包含整数 N,表示顶点数量。
第二行包含 N 个整数,依次为顶点 1 至顶点 N 的权值。
输出格式
输出仅一行,为所有三角形的顶点权值乘积之和的最小值。
数据范围
N≤50,
数据保证所有顶点的权值都小于109
样例
输入样例:
5
121 122 123 245 231
输出样例:
12214884
方法一 :__int128
C++ 代码
#include<iostream>
#include<bits/stdc++.h>
using namespace std ;
const int N = 55 ;
const __int128 INF = 1e27 ; // INF的 类型要写成 const __int128 !!
inline __int128 read(){
__int128 x = 0, f = 1;
char ch = getchar();
while(ch < '0' || ch > '9'){
if(ch == '-')
f = -1;
ch = getchar();
}
while(ch >= '0' && ch <= '9'){
x = x * 10 + ch - '0';
ch = getchar();
}
return x * f;
}
inline void print(__int128 x){
if(x < 0){
putchar('-');
x = -x;
}
if(x > 9)
print(x / 10);
putchar(x % 10 + '0');
}
__int128 f[N][N];
__int128 p[N];
int main(){
int a, n , m ;
cin >> n ;
for(int i = 1 ; i <= n ; i ++){
p[i] = read() ;
}
/*
状态表示 : 以 le 为左点 , ri 为 右点的 三角形 表示的方案大小
*/
for(int len = 3 ; len <= n ; len ++){ // 当 len 为2 时 无意义
for(int le = 1 ; le + len -1 <= n ; le ++){
int ri = le + len - 1 ;
f[le][ri] = INF ;
for(int k = le+1 ; k < ri ; k ++){ // 枚举的点不能和 左右区间 重合 !
f[le][ri] = min(f[le][ri] , f[le][k] + f[k][ri] + (p[le] * p[k] * p[ri])) ;
}
}
}
print(f[1][n]) ;
return 0 ;
}
方法二 :手写高精度
C++ 代码
// 高精度 !!
#include<iostream>
#include<bits/stdc++.h>
using namespace std ;
typedef long long LL ;
const int N = 55 , M = 35 , INF = 1e27 ;
LL w[N] ;
LL f[N][N][M] ; // 最后一维用来存 数字的 从0 开始存 ,低位在0 ,高位在 M ;
void add(LL a[] , LL b[]) // 低位在0 高位在 M处 , 加法从 0 加到 M
{
static LL c[M] ;
memset(c , 0 , sizeof c) ;
LL t = 0 ;
for(int i = 0 ; i < M ; i ++){
t += a[i] + b[i] ;
c[i] = t %10 ;
t /= 10 ;
}
memcpy(a , c , sizeof c) ;
}
void mul(LL a[] , LL b) // 低位在0 高位在 M处 , 加法从 0 加到 M
{
static LL c[M] ;
memset(c , 0 , sizeof c) ;
LL t = 0 ;
for(int i = 0 ; i < M ; i ++){
t += a[i] * b ;
c[i] = t%10 ;
t /= 10 ;
}
memcpy(a , c , sizeof c) ;
}
int cmp(LL a[] , LL b[]) // 因为 高位在M处 所以比较的时候 从高位开始向下比较 M -> 0 ;
{
for(int i = M - 1; i >= 0 ; i --){
if(a[i] > b[i]) return 1 ;
else if(b[i] > a[i]) return 0 ;
}
return 0 ;
}
void print(LL a[]) // 输出的时候 也是 从高位开始输出 M -> 0 ;
{
int k = M - 1 ;
while(k && !a[k]) k -- ; // 删去前导零 !!
while(k >= 0 ) cout << a[k --] ;
cout << '\n' ;
}
int main(){
int a, n , m ;
cin >> n ;
for(int i = 1 ; i <= n ; i ++){
cin >> w[i] ;
}
LL tmp[M] ;
for(int len = 3 ; len <= n ; len ++){
for(int le = 1 ; le + len - 1 <= n ; le ++){
int ri = le+ len - 1 ;
f[le][ri][M -1] = 1 ;
for(int k = le + 1 ; k < ri ; k ++){
memset( tmp , 0 , sizeof tmp) ;
// 原本写法是这样
// f[le][ri] = min(f[le][ri] , f[le][k] + f[k][ri] + (w[le] * w[k] * w[ri])) ;
tmp[0] = w[le] ; // 第一个要乘的数 直接 赋值到 tmp[]数组里面
mul(tmp , w[k] ) ;
mul(tmp , w[ri]) ;
add(tmp , f[le][k]) ;
add(tmp , f[k][ri]) ;
if(cmp(f[le][ri] , tmp) > 0){
memcpy(f[le][ri] , tmp , sizeof tmp) ; // 直接赋值
}
}
}
}
print(f[1][n]) ;
return 0 ;
}