题意
给定常数 \(k\),一棵 \(n\) 节点的树和序列 \(d\)(\(d\) 单调不降),选定一些点为关键点。设关键点的个数为 \(cnt\),集合为 \(S\),求
\[\min\{k\cdot cnt\cdot\sum_{i=1}^n\max_{j\in S}\{d_{dist_{i,j}}\}\} \]sol
显然树形 DP。
由于 \(d\) 单调不降,因此每个点一定会尽可能选择更接近的关键点,因此,选同一点的所有点一定构成一个连通块。这样我们就可以进行树形 DP 了。
状态:\(f_{u,j}\) 表示在以 \(u\) 为根的子树中,\(u\) 选取的关键点为 \(j\) 的最小代价。
转移:对于每一个儿子,我们可以枚举它的所有关键点,此时,如果它选取的关键点与父亲选取的关键点相同,说明两节点选重,因此还需要减少 \(k\),即:
这样做时间复杂度是 \(O(n^3)\),能够通过此题,但可以优化。
我们记录 \(ans_u\),表示使 \(f_{u,j}\) 最小的 \(j\),这样,原式即转化为了:
输出方案:我们可以按照由根至下的顺序递归,记录转移到 \(u\) 的点。显然,仅当 \(f_{father,ans_{father}} - k < f_{u,ans_u}\) 时,转移到 \(u\) 的点才为 \(ans_{father}\),否则为 \(ans_u\),并记录到 \(ans\) 中。
代码
#include <iostream>
#include <algorithm>
#include <cstring>
using namespace std;
const int N = 205;
int d[N];
int h[N], e[N * 2], ne[N * 2], idx;
int dist[N][N];
int f[N][N], ans[N];
int n, k;
void add(int a, int b){
e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ;
}
void floyd(){
for (int k = 1; k <= n; k ++ )
for (int i = 1; i <= n; i ++ )
for (int j = 1; j <= n; j ++ )
dist[i][j] = min(dist[i][j], dist[i][k] + dist[k][j]);
}
void dfs(int u, int father){
for (int i = 1; i <= n; i ++ ) f[u][i] = k + d[dist[i][u]];
for (int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if (j == father) continue;
dfs(j, u);
for (int t = 1; t <= n; t ++ )
f[u][t] += min(f[j][t] - k, f[j][ans[j]]);
}
ans[u] = 1;
for (int i = 2; i <= n; i ++ )
if (f[u][i] < f[u][ans[u]]) ans[u] = i;
}
void print(int u, int fa){
if (fa > 0 && f[u][ans[fa]] - k < f[u][ans[u]]) ans[u] = ans[fa];
for (int i = h[u]; ~i; i = ne[i]){
int j = e[i];
if (j == fa) continue;
print(j, u);
}
}
int main(){
memset(h, -1, sizeof h);
scanf("%d%d", &n, &k);
for (int i = 1; i < n; i ++ ) scanf("%d", &d[i]);
memset(dist, 0x3f, sizeof dist);
for (int i = 1; i <= n; i ++ ) dist[i][i] = 0;
for (int i = 1; i < n; i ++ ) {
int u, v;
scanf("%d%d", &u, &v);
add(u, v), add(v, u);
dist[u][v] = dist[v][u] = 1;
}
floyd();
dfs(1, -1);
printf("%d\n", f[1][ans[1]]);
print(1, -1);
for (int i = 1; i <= n; i ++ ) printf("%d ", ans[i]);
return 0;
}
标签:luoguCF70E,dist,idx,Reform,int,min,lnsyoj70E,ans,关键点
From: https://www.cnblogs.com/XiaoJuRuoUP/p/-/lnsyoj70E_luoguCF70E