加分二叉树
题目要求
题目描述：
输入格式：
第 1 行：一个整数 n ，为节点个数。
第 2 行：n 个用空格隔开的整数，为每个节点的分数（0 < 分数 < 100 ）。
输出格式：
第 1 行：一个整数，为最高加分（结果不会超过int范围）。
第 2 行：n 个用空格隔开的整数，为该树的前序遍历。如果存在多种方案，则输出字典序最小的方案。
数据范围：
n<30
输入样例：
5 5 7 1 2 10
输出样例：
145 3 1 2 4 5
思路分析
代码
#include <iostream> #include <cstring> #include <algorithm> using namespace std; const int N = 35; int n; int w[N]; int f[N][N]; // 存储从 [i, j] 的最高分 int g[N][N]; // 存储从 [i, j] 的根节点 void print(int l, int r) { if (l > r) return; cout << g[l][r] << ' '; print(l, g[l][r] - 1); // 递归左子树 print(g[l][r] + 1, r); // 递归右子树 } int main() { cin >> n; for (int i = 1; i <= n; i ++ ) cin >> w[i]; for (int len = 1; len <= n; len ++ ) for (int l = 1; l + len - 1 <= n; l ++ ) { int r = l + len - 1; if (len == 1) f[l][r] = w[l], g[l][r] = l; else for (int k = l; k <= r; k ++ ) { int left = k == l ? 1 : f[l][k - 1]; int right = k == r ? 1 : f[k + 1][r]; int score = left * right + w[k]; if (f[l][r] < score) { f[l][r] = score; g[l][r] = k; } } } cout << f[1][n] << endl; print(1, n); // 递归输出前序遍历 return 0; }
凸多边形的划分
题目要求
题目描述：
给定一个具有 N 个顶点的凸多边形，将顶点从 1 至 N 标号，每个顶点的权值都是一个正整数。
将这个凸多边形划分成 N − 2 个互不相交的三角形，对于每个三角形，其三个顶点的权值相乘都可得到一个权值乘积，试求所有三角形的顶点权值乘积之和至少为多少。
输入格式：
第一行包含整数 N ，表示顶点数量。
第二行包含 N 个整数，依次为顶点 1 至顶点 N 的权值。
输出格式：
输出仅一行，为所有三角形的顶点权值乘积之和的最小值。
数据范围：
N≤50,
数据保证所有顶点的权值都小于109
输入样例：
5 121 122 123 245 231
输出样例：
12214884
思路分析
代码
#include <iostream> #include <cstring> #include <algorithm> #include <vector> using namespace std; typedef long long LL; const int N = 55; int n; int w[N]; vector<int> f[N][N]; bool 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 true; } 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; } while (t) c.push_back(t % 10), t /= 10; return c; } vector<int> mul(vector<int> a, LL b) { vector<int> c; LL t = 0; for (int i = 0; i < a.size(); i ++ ) { t += b * a[i]; c.push_back(t % 10); t /= 10; } while (t) c.push_back(t % 10), t /= 10; return c; } int main() { scanf("%d", &n); for (int i = 1; i <= n; i ++ ) scanf("%d", &w[i]); //区间DP //此处初始状态f[l][l+1] = 0 初始就是空vector，不用额外设置 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) { //w_l * w_k * w_r auto new_val = mul(mul({w[l]}, w[k]), w[r]); // {w[l]}可以直接初始化为一个vector //f[l][k] + f[k][r] + cost new_val = add(add(new_val, f[l][k]), f[k][r]); //f[l][r] = min(f[l][r], f[l][k] + f[k][r] + w_sum) if (f[l][r].empty() || cmp(new_val, f[l][r])) f[l][r] = new_val; } } } //输出最终答案 auto res = f[1][n]; for (int i = res.size() - 1; i >= 0; i -- ) printf("%d", res[i]); puts(""); return 0; }
