首页 > 代码库 > HDU 4003 (树形DP+背包)
HDU 4003 (树形DP+背包)
题目链接: http://acm.hdu.edu.cn/showproblem.php?pid=4003
题目大意：有K个机器人，走完树上的全部路径，每条路径有个消费。对于一个点，机器人可以出去再回来，开销2倍。也可以不回来，一直停在某个点（如果你的机器人数量足够多的话）。问最小开销。
解题思路：
其实这题只能说是类树形背包。
用dp[i][j]表示在i点，有j个不回来的机器人走过的最小开销。
比如dp[i][0]就表示，i点及其子点全部靠其它点的不回来的机器人探索。所以机器人是一来一回开销2倍。
for(K...j...0) //j可以为0
dp[i][j]+=dp[t][0]+2*e[a].w; //表示子点t全靠其它点的机器人探索
for(1..k....j) //k要从1开始了，且k最大可以为j，也就是说父亲点可以是0个机器人，子点的机器人下去之后又回到子点，又去探索新的子点的子点。这样必然有父亲点0的情况。
dp[i][j]=min(dp[i][j],dp[i][j-k]+dp[t][k]+k*e.w); //权在边的计算模板
#include "cstdio"#include "vector"#include "iostream"#include "cstring"using namespace std;#define maxn 10005struct Edge{ int to,next,w;}e[maxn*2];int dp[maxn][15],head[maxn],tol;int n,s,K,u,v,w;void addedge(int u,int v,int w){ e[tol].to=v; e[tol].next=head[u]; e[tol].w=w; head[u]=tol++;}void dfs(int root,int pre){ int i=root; for(int a=head[root];a!=-1;a=e[a].next) { int t=e[a].to; if(t==pre) continue; dfs(t,root); for(int j=K;j>=0;j--) { dp[i][j]+=dp[t][0]+2*e[a].w; for(int k=1;k<=j;k++) dp[i][j]=min(dp[i][j],dp[i][j-k]+dp[t][k]+k*e[a].w); } }}int main(){ //freopen("in.txt","r",stdin); while(~scanf("%d%d%d",&n,&s,&K)) { memset(dp,0,sizeof(dp)); memset(head,-1,sizeof(head)); tol=0; for(int i=1;i<n;i++) { scanf("%d%d%d",&u,&v,&w); addedge(u,v,w); addedge(v,u,w); } dfs(s,s); printf("%d\n",dp[s][K]); }}
| 2882723 | neopenx | HDU | 4003 | Accepted | 1092 | 265 | C++ | 1072 | 2014-10-24 12:36:57 |
HDU 4003 (树形DP+背包)
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。