首页 > 其他分享 >[lnsyoj70E/luoguCF70E]Information Reform

[lnsyoj70E/luoguCF70E]Information Reform

时间:2024-08-08 19:38:29浏览次数:11  
标签:luoguCF70E dist idx Reform int min lnsyoj70E ans 关键点

题意

给定常数 \(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\),即:

\[f_{u,j}=dist_{u,j} + \sum_{v\in u_{son}}\min\{f_{v, j}-k,\min_{i=1}^n\{f_{v,i}\}\} \]

这样做时间复杂度是 \(O(n^3)\),能够通过此题,但可以优化。
我们记录 \(ans_u\),表示使 \(f_{u,j}\) 最小的 \(j\),这样,原式即转化为了:

\[f_{u,j}=dist_{u,j} + \sum_{v\in u_{son}}\min\{f_{v, j}-k,f_{v,ans_v}\} \]

输出方案:我们可以按照由根至下的顺序递归,记录转移到 \(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

相关文章

  • 题解 CF70E【Information Reform】
    题解CF70E【InformationReform】题目描述\(n\)个点的树,边权为\(1\)。可以花费常数\(k\),在一个点上建基站。每个点\(i\)需要找到离他最近的基站\(a_i\),花费\(d[dis(i,a_i)]\)。一种方案的总花费是建基站的花费加上每个点的花费之和。最小化总花费。输出方案\(a_i\)。......
  • CF1468J Road Reform 题解
    题目简述给定一个有$n$个节点,$m$条无向带权边的图,和一个参数$k$,第$i$条边权值为$s_i$。现在你要保留这个图中的$n-1$条边使得这个图变成一棵树,然后你可以对这棵树上的任意边进行修改,每次修改可以使这个边的权值加上一或减去一。现在你需要使所有边权的最大值正好等于......
  • Reformer 模型 - 突破语言建模的极限
    Reformer如何在不到8GB的内存上训练50万个词元Kitaev、Kaiser等人于20202年引入的Reformer模型是迄今为止长序列建模领域内存效率最高的transformer模型之一。最近,人们对长序列建模的兴趣激增,仅今年一年,就涌现出了大量的工作,如Beltagy等人的工作(2020)、Roy等......
  • CF723E One-Way Reform
    很有意思的一个题,刚开始想复杂了后面看了题解才发现是个傻逼题首先不难发现答案的上界数就是度数为偶数的节点数,考虑一种构造方法能打到这个上界不妨新建一个虚拟节点,将所有度数为奇数的点与其连边,这样图中所有点度数都变成了偶数,包括这个虚拟节点而对于一个所有点度数均为偶数......
  • win10 CUDA11.1安装torch1.9 / reformer_pytorch
    环境NVIDIA-SMI457.52DriverVersion:457.52CUDAVersion:11.1安装torch-gpucondacreate-ntorch1.9python=3.8pipinstalltorch==1.9.1+cu111torchvision==0.10.1+cu111torchaudio==0.9.1-fhttps://download.pytorch.org/whl/torch_stable.htmlc......
  • pycharm设置保存时自动格式化代码(Auto Reformat Code)
    原文:https://blog.csdn.net/qq_41906934/article/details/1246318261.手动格式化代码Code->ReformatCode格式化快捷键为Ctrl+Alt+L,但是可能和锁屏快捷键冲突,下面介绍如何配置保存时自动格式化代码2.保存格式化代码安装FileWatchers插件FileWatchers插件在安装Pych......
  • Codeforces Round #346 (Div. 2)-E. New Reform
    原题链接E.NewReformtimelimitpertestmemorylimitpertestinputoutputn citiesconnectedby m bidirectionalroads.Noroadconnectsacitytoitself,andeachpairofcitiesisconnectedbynomorethan......
  • The Importance of Particle Size Analysis in Preformulation Studies
    Thesizeoftheparticlesiscalledparticlesize.TheparticlesizeoftheAPIiscloselyrelatedtothehomogeneityofthepreparationprocessintermsofmixing,theaccuracyofdosage,andcompressibility,andithasanimpactonthesolubility,durat......