小单刷题笔记之——区间DP
🎁题目: 凸多边形的划分
给定一个具有 N 个顶点的凸多边形,将顶点从 1 至 N 标号,每个顶点的权值都是一个正整数。 将这个凸多边形划分成 N−2个互不相交的三角形,对于每个三角形,其三个顶点的权值相乘都可得到一个权值乘积,试求所有三角形的顶点权值乘积之和至少为多少。 输入格式 第一行包含整数 N,表示顶点数量。 第二行包含 N 个整数,依次为顶点 1 至顶点 N 的权值。 输出格式 输出仅一行,为所有三角形的顶点权值乘积之和的最小值。 数据范围 N≤50, 数据保证所有顶点的权值都小于10^9 输入样例: 5 121 122 123 245 231 输出样例: 12214884
想到这道题实际上不是一个环状DP,而是一个链状DP,就差不多搞定了,定义f (i , j )为所有将L - R这个封闭凸多边形划分成N - 2个三角形方案中的权值最小情况。写完记得上个高精就行。
然后就是区间DP:
for len
for 端点
for 分割点
#include <cstring> #include <iostream> #include <algorithm> using namespace std; typedef long long LL; const int N = 55, M = 35, INF = 1e9; int n; int w[N]; LL f[N][N][M]; void add(LL a[], LL b[]) { LL c[M]; memset(c, 0, sizeof c); for (int i = 0, t = 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) { 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[]) { for (int i = M - 1; i >= 0; i -- ) if (a[i] > b[i]) return 1; else if (a[i] < b[i]) return -1; return 0; } void print(LL a[]) { int k = M - 1; while (k && !a[k]) k -- ; while (k >= 0) cout << a[k -- ]; 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 l = 1; l + len - 1 <= n; l ++ ) { int r = l + 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; }
上一篇:
IDEA上Java项目控制台中文乱码