题解 | #小d和送外卖#

小d和答案修改

https://ac.nowcoder.com/acm/contest/53366/A

一道典型的树形背包,看到n,k值 m<=50 果断用m做完背包第2维,就是选不选的普遍问题了

dp[i][j]:以节点i为根节点子树中没选j个点情况下的最短路径,相当于用了一个滚动数组优化了一个维度 下面直接上代码,里面有过程注释

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int inf = 0x3f3f3f3f;
const int N = 2e5+8;
typedef long long ll;
int n,m,k,dp[N][60],cnt[N],tmp[60];
vector<int>e[N];
void dfs(int cur,int fa){
    for(int i=0;i<e[cur].size();i++){
        int now = e[cur][i];
        if(now==fa)continue;
        dfs(now,cur);
        cnt[cur]+=cnt[now];
        //dp[i][j][m] 因为是树形dp 相当于自然列举了j个待选项
        //相当于直接用滚动数组优化掉了第2维度 到第j个为止
        //dp[i][j]节点i为根节点子树没选j个点情况下最小路径
        //可以用一个数组巧妙的不断重置来替代滚动数组
        memset(tmp,inf,sizeof(tmp));
        for(int j=0;j<=min(cnt[cur],m);j++){//cur节点子树不选j个时
            for(int k=0;k<=min(cnt[now],j);k++){//当前子节点不选k个时
                tmp[j]=min(tmp[j],dp[cur][j-k]+dp[now][k]+(k==cnt[now]?0:2));
                //若k==cnt[now]就是子树全部放弃不需要再往下走
            }
        }
        memcpy(dp[cur],tmp,sizeof(tmp));
    }
}
signed main()
{
    cin>>n>>m;
    for(int i=1;i<=n-1;i++){
        int u,v;
        cin>>u>>v;
        e[u].push_back(v);
        e[v].push_back(u);
    }
    cin>>k;
    for(int i=1;i<=k;i++){
        int x;
        cin>>x;
        cnt[x]++;
    }
    dfs(1,0);
    cout<<dp[1][min(m,k)]<<'\n';
    return 0;
}

全部评论

相关推荐

一表renzha:手写数字识别就是一个作业而已
点赞 评论 收藏
分享
来个大佬救一下,为上投了都是石沉大海了,没实习经历的话怕秋招直接进不了面。什么实习这么难找,基本
心态爆炸了:现在正式的岗位都少,实习基本不咋招的,除了大厂,中小企业其实没那么多岗位需求,就算是有,大多都是招一两个廉价劳动力,同时,他们也会希望你一来就能干活的,没时间培训你,就让你了解公司的项目,你了解完就可以开始干活。再者是,很多低质量的实习其实用处没有那么大的。我去年也是找实习找到破防,最后去了一家深圳的小公司实习,工作对我来说很简单,甚至不如我在学校做的项目,秋招的时候,这段实习经历也并没有帮上什么忙,投递简历,依旧非常低的回复率。低回复率是常态,尤其是找实习,找不到,那就把重心放在优化自己的简历和项目,多看八股文,锻炼自己的面试能力,多看别人的面经,自己模拟面试,等秋招的时候,只要有那么寥寥几次,好好抓住那几次机会。
点赞 评论 收藏
分享
评论
3
收藏
分享

创作者周榜

更多
牛客网
牛客网在线编程
牛客网题解
牛客企业服务