洛谷P3177 [HAOI2015]树上染色(树上背包)
程序员文章站
2022-04-30 09:46:46
题意 "题目链接" Sol 比较套路吧,设$f[i][j]$表示以$i$为根的子树中选了$j$个黑点对答案的贡献 然后考虑每条边的贡献,边的两边的答案都是可以算出来的 转移的时候背包一下。 cpp include define Pair pair define fi first define se ......
题意
sol
比较套路吧,设\(f[i][j]\)表示以\(i\)为根的子树中选了\(j\)个黑点对答案的贡献
然后考虑每条边的贡献,边的两边的答案都是可以算出来的
转移的时候背包一下。
#include<bits/stdc++.h> #define pair pair<int, int> #define fi first #define se second #define mp(x, y) make_pair(x, y) #define ll long long const int maxn = 2001, inf = 1e9 + 7; using namespace std; inline int read() { int x = 0, f = 1; char c = getchar(); while (c < '0' || c > '9') {if (c == '-') f = -1; c = getchar();} while (c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar(); return x * f; } int n, k, siz[maxn]; ll f[maxn][maxn]; vector<pair> v[maxn]; void dfs(int x, int fa) { siz[x] = 1; f[x][1] = f[x][0] = 0; for(int i = 0; i < v[x].size(); i++) { int to = v[x][i].fi, w = v[x][i].se; if(to == fa) continue; dfs(to, x); siz[x] += siz[to]; } for(int i = 0; i < v[x].size(); i++) { int to = v[x][i].fi, w = v[x][i].se; if(to == fa) continue; for(int j = min(siz[x], k); j >= 0; j--) for(int k = 0; k <= min(siz[to], j); k++) if(f[x][j - k] >= 0) f[x][j] = max(f[x][j], f[x][j - k] + f[to][k] + 1ll * k * (k - k) * w + 1ll * (siz[to] - k) * (n - (k - k) - siz[to]) * w); } } main() { n = read(); k = read(); for(int i = 1; i <= n - 1; i++) { int x = read(), y = read(), w = read(); v[x].push_back(mp(y, w)); v[y].push_back(mp(x, w)); } memset(f, -0x7f, sizeof(f)); dfs(1, 0); cout << f[1][k]; return 0; }
上一篇: IOS之高德地图显示出地图并定位成功