1571：【例 3】凸多边形的划分

时间限制: 1000 ms 内存限制: 524288 KB
提交数: 1114 通过数: 324
【题目描述】
给定一个具有 N 个顶点的凸多边形，将顶点从 1 至 N 标号，每个顶点的权值都是一个正整数。将这个凸多边形划分成 N−2 个互不相交的三角形，试求这些三角形顶点的权值乘积和至少为多少。

【输入】
输入第一行为顶点数 N
第二行依次为顶点 1 至顶点 N 的权值。

【输出】
输出仅一行，为这些三角形顶点的权值乘积和的最小值。

【输入样例】
5
121 122 123 245 231
【输出样例】
12214884
【提示】
数据范围与提示：

对于 100% 的数据，有 N≤50，每个点权值小于 109 。

感觉是比较基础的区间dp
和能量项链那道题差不多，就是高精度烦人，不想写了，嫖了一篇题解

代码：

#include<cstdio>
#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
const int maxn = 65;
inline void qread(int &x) {
	x = 0;
	register int ch = getchar();
	while(ch < '0' || ch > '9')    ch = getchar();
	while(ch >= '0' && ch <= '9')    x = 10 * x + ch - 48, ch = getchar();
}
struct bignum {
	int num[40];
	bignum() {
		num[0] = 1;
	}
	void set(int x) {
		memset(num, 0, sizeof(num));
		while(x) {
			num[++num[0]] = x % 10;
			x /= 10;
		}
		if(!num[0])    num[0] = 1;
	}
	void clear() {
		memset(num, 0, sizeof(num));
		num[0] = 1;
	}
	void INF() {
		num[0] = 30;
		num[num[0]] = 9;
	}
};
bignum minn(const bignum &a, const bignum &b) {
	if(a.num[0] > b.num[0])    return b;
	if(a.num[0] < b.num[0])    return a;
	for(int i = a.num[0]; i >= 1; --i) {
		if(a.num[i] > b.num[i])    return b;
		if(a.num[i] < b.num[i])    return a;
	}
	return a;
}
bignum add(bignum a, bignum b) {
	bignum c;
	c.clear();
	c.num[0] = max(a.num[0], b.num[0]);
	int jw = 0;
	for(int i = 1; i <= c.num[0]; ++i) {
		c.num[i] = a.num[i] + b.num[i] + jw;
		jw = c.num[i] / 10;
		if(jw)    c.num[i] -= 10;
	}
	if(jw)    c.num[++c.num[0]] = jw;
	return c;
}
bignum mul(bignum a, bignum b) {
	bignum c;
	c.clear();
	c.num[0] = a.num[0] + b.num[0];

	for(int i = 1; i <= a.num[0]; ++i) {
		int jw = 0;
		for(int j = 1; j <= b.num[0]; ++j) {
			c.num[i + j - 1] += a.num[i] * b.num[j] + jw;
			jw = c.num[i + j - 1] / 10;
			c.num[i + j - 1] %= 10;
		}
		c.num[i + b.num[0]] = jw;
	}
	while(c.num[c.num[0]] == 0)
		--c.num[0];
	if(!c.num[0])    c.num[0] = 1;
	return c;
}
void show(const bignum &a) {
	for(int i = a.num[0]; i >= 1; --i)
		putchar(a.num[i] + 48);
}
int n;
bignum data[maxn << 1];
bignum dp[maxn << 1][maxn << 1];
int main(void) {
	qread(n);
	for(int i = 1; i <= n; ++i) {
		int x;
		qread(x);
		data[i].set(x);
		data[i + n] = data[i];
	}
	data[n << 1 | 1] = data[1];
	for(int i = 1; i < n; i++)
		dp[i][i + 1].set(0);
	for(int i = 2; i < n; i++)
		for(int j = 1; j <= n - i; j++) {
			dp[j][j + i].INF();
			for(int k = j + 1; k < i + j; k++)
				dp[j][j + i] = minn(dp[j][j + i], add(add(dp[j][k], dp[k][j + i]), mul(mul(data[i + j], data[j]), data[k])));

		}
	show(dp[1][n]);
}