题目描述
给定一个具有 N个顶点的凸多边形,将顶点从1至N标号,每个顶点的权值都是一个正整数。将这个凸多边形划分成N−2个互不相交的三角形,对于每个三角形,其三个顶点的权值乘都可得到一个权值,试求所有三角形的顶点权值乘积之和至少为多少。
输入格式:
第一行包含整数 N,表示顶点数量。
第二行包含 N个整数,依次为顶点 1至顶点 N的权值。
输出格式:
输出仅一行,为所有三角形的顶点权值乘积之和的最小值。
数据范围
N ≤ 50,
数据保证所有顶点的权值都小于109
样例
输入样例:
5
121 122 123 245 231
输出样例:
12214884
算法1
(暴力枚举)
C++ 代码
不加高精度的写法(WA) 5/11
#include <iostream>
using namespace std;
const int N = 50, INF = 0x3f3f3f3f;
typedef long long LL;
int n;
int w[N];
LL f[N][N];
int main()
{
cin >> n;
for(int i = 1 ; i <= n ; i ++) cin >> w[i];
for(int len = 3 ; len <= n ; len ++)
for(int i = 1 ; i + len - 1 <= n ; i ++)
{
int l = i, r = i + len - 1;
f[l][r] = INF;
for(int k = l + 1 ; k < r ; k ++)
{
f[l][r] = min(f[l][r], f[l][k] + f[k][r] + w[l] * w[r] * w[k]);
}
}
cout << f[1][n] << endl;
return 0;
}
算法2
C++ 代码
使用高精度的写法:
#include <iostream>
#include <cstring>
using namespace std;
typedef long long LL;
const int N = 210, M = 35, INF = 0x3f3f3f3f;
int n;
int w[N];
LL f[N][N][M];
int cmp(LL a[], LL b[])
{
for(int i = M - 1 ; i >= 0 ; i --)//直接从高位进行比较
{
if(a[i] > b[i]) return 1;
if(a[i] < b[i]) return -1;
}
return 0;
}
void add(LL a[], LL b[])
{
static LL temp[M];
memset(temp, 0, sizeof temp);
for(int i = 0, t = 0 ; i < M ; i ++)
{
t += a[i] + b[i];
temp[i] = t % 10;
t /= 10;
}
memcpy(a, temp, sizeof temp);
}
void mul(LL a[], LL b)
{
LL temp[M];
LL t = 0;
memset(temp, 0, sizeof temp);
for(int i = 0 ; i < M ; i ++)
{
t += a[i] * b;
temp[i] = t % 10;
t /= 10;
}
memcpy(a, temp, sizeof temp);
}
void print(LL a[])
{
int k = M - 1;
while(k && !a[k]) k --;
for(int i = k ; i >= 0 ; i --)
cout << a[i];
cout << endl;
}
int main()
{
cin >> n;
for(int i = 1 ; i <= n ; i ++) cin >> w[i];
LL temp[M];
for(int len = 3 ; len <= n ; len ++)
for(int i = 1 ; i + len - 1 <= n ; i ++)
{
int l = i, r = i + len - 1;
f[l][r][M - 1] = 1;
for(int k = l + 1 ; k < r ; k ++)
{
memset(temp, 0, sizeof temp);
temp[0] = w[l];
mul(temp, w[k]);
mul(temp, w[r]);
add(temp, f[l][k]);
add(temp, f[k][r]);
if(cmp(f[l][r], temp) > 0) memcpy(f[l][r], temp, sizeof temp);
}
}
print(f[1][n]);
return 0;
}