C++|2021-10-19（树形dp）动态规划|ACWing算法提高课

1069. 凸多边形的划分给定一个具有 N 个顶点的凸多边形，将顶点从 1 至 N 标号，每个顶点的权值都是一个正整数。
将这个凸多边形划分成 N?2 个互不相交的三角形，对于每个三角形，其三个顶点的权值相乘都可得到一个权值乘积，试求所有三角形的顶点权值乘积之和至少为多少。
输入格式
第一行包含整数 N，表示顶点数量。
第二行包含 N 个整数，依次为顶点 1 至顶点 N 的权值。
输出格式
输出仅一行，为所有三角形的顶点权值乘积之和的最小值。
数据范围
N≤50,
数据保证所有顶点的权值都小于109
输入样例：

5 121 122 123 245 231

输出样例：
12214884

#include using namespace std; typedef long long LL; const int N = 55; int n; int w[N]; vectorf[N][N]; bool cmp(vector& a, vector& 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; } vectoradd(vector a, vector b) { vectorc; int t = 0; for (int i = 0; i <(int) a.size() || i <(int) b.size(); i++) {if (i <(int) a.size())t += a[i]; if (i < (int)b.size())t += b[i]; c.push_back(t % 10); t /= 10; } while (t) {c.push_back(t % 10); t /= 10; } return c; } vectormul(vectora, LL b) { vectorc; LL t = 0; for (int i = 0; i < (int)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() { cin >> n; for (int i = 1; i <= n; i++)cin >> w[i]; for (int len = 3; len <= n; len++) {for (int l = 1, r = 0; l + len - 1 <= n; l++) {r = l + len - 1; for (int k = l + 1; k < r; k++) {auto val = mul(mul({ w[l] }, w[k]), w[r]); val = add(add(val, f[l][k]), f[k][r]); if (f[l][r].empty() || cmp(val, f[l][r]))f[l][r] = val; } } } auto res = f[1][n]; for (int i = res.size() - 1; i >= 0; i--)cout << res[i]; puts(""); return 0; }

1072. 树的最长路径给定一棵树，树中包含 n 个结点（编号1~n）和 n?1 条无向边，每条边都有一个权值。
现在请你找到树中的一条最长路径。
换句话说，要找到一条路径，使得使得路径两端的点的距离最远。
注意：路径中可以只包含一个点。
输入格式
第一行包含整数 n。
接下来 n?1 行，每行包含三个整数 ai,bi,ci，表示点 ai 和 bi 之间存在一条权值为 ci 的边。
输出格式
输出一个整数，表示树的最长路径的长度。
数据范围
1≤n≤10000,
1≤ai,bi≤n,
?105≤ci≤105
输入样例：

6 5 1 6 1 4 5 6 3 9 2 6 8 6 1 7

输出样例：
22

#include using namespace std; const int N = 1e4 + 10, M = N << 1; int n; int h[N], e[M], w[M], ne[M], idx; int f1[N], f2[N], res; void add(int a, int b, int c) { e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++; } void dfs(int u, int father) { f1[u] = f2[u] = 0; for (int i = h[u]; ~i; i = ne[i]) {int j = e[i]; if (j == father)continue; dfs(j, u); if (f1[j] + w[i] >= f1[u])f2[u] = f1[u], f1[u] = f1[j] + w[i]; else if (f1[j] + w[i] > f2[u])f2[u] = f1[j] + w[i]; } res = max(res, f1[u] + f2[u]); } int main() { memset(h, -1, sizeof h); cin >> n; for (int i = 0; i < n - 1; i++)//n-1条边 {int a, b, c; cin >> a >> b >> c; add(a, b, c); add(b, a, c); } dfs(1, -1); cout << res << endl; return 0; }

1073. 树的中心给定一棵树，树中包含 n 个结点（编号1~n）和 n?1 条无向边，每条边都有一个权值。
请你在树中找到一个点，使得该点到树中其他结点的最远距离最近。
输入格式
第一行包含整数 n。
接下来 n?1 行，每行包含三个整数 ai,bi,ci，表示点 ai 和 bi 之间存在一条权值为 ci 的边。
输出格式
输出一个整数，表示所求点到树中其他结点的最远距离。
【C++|2021-10-19（树形dp）】数据范围
1≤n≤10000,
1≤ai,bi≤n,
1≤ci≤105
输入样例：
5
2 1 1
3 2 1
4 3 1
5 1 1
输出样例：
2

#include using namespace std; const int N = 1e5 + 10, M = 2 * N, INF = 1e9; int d1[N], d2[N], up[N], p1[N], p2[N]; int h[N], ne[M], e[M], w[M], idx; int n; void add(int a, int b, int c) { e[idx] = b; w[idx] = c; ne[idx] = h[a]; h[a] = idx++; } int dfs_down(int u, int father)//返回u的最长向下路径 { d1[u] = d2[u] = -INF; for (int i = h[u]; ~i; i = ne[i]) {int j = e[i]; if (j == father)continue; int dist = dfs_down(j, u) + w[i]; if (dist > d1[u])//更新最长和第二长 {d2[u] = d1[u]; d1[u] = dist; p2[u] = p1[u]; p1[u] = j; } else if (dist > d2[u]) {d2[u] = dist; p2[u] = j; } } if (d1[u] == -INF)d1[u] = d2[u] = 0; //叶节点 return d1[u]; } void dfs_up(int u, int father)//用父节点更新子节点向上最长路径 { for (int i = h[u]; ~i; i = ne[i]) {int j = e[i]; if (j == father)continue; if (p1[u] == j)up[j] = max(up[u], d2[u]) + w[i]; else up[j] = max(up[u], d1[u]) + w[i]; dfs_up(j, u); } } int main() { cin >> n; memset(h, -1, sizeof h); for (int i = 0; i < n - 1; i++) {int a, b, c; cin >> a >> b >> c; add(a, b, c); add(b, a, c); } dfs_down(1, -1); dfs_up(1, -1); int res = INF; for (int i = 1; i <= n; i++)res = min(res, max(d1[i], up[i])); cout << res << endl; return 0; }