本文共 1158 字，大约阅读时间需要 3 分钟。

1、

2、题目大意：

一棵树有n个结点，根节点是s,在树上放k个机器人，现在使得k个机器人将所有结点遍历一遍最小的代价是多少？

dp[i][j]表示以i为根节点放j个机器人消耗的最小代价，

因为必须选择选择每个分组中的一个，我们可以将dp[u][0]先放进去，如果有更好的再替换它

for(int j=m;j>=0;j--)

            {                 dp[u][j]+=dp[vv][0]+w[i]*2;                 for(int k=1;k<=j;k++)                 {                     dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[vv][k]+k*w[i]);                 }             }

3、AC代码;

#include
   
    #include
    
     #include
     
      using namespace std;#define N 10005int head[N*2],next[N*2],v[N*2],w[N*2];int tot,m;int dp[N][15];void add_edge(int a,int b,int c){    v[tot]=b;    w[tot]=c;    next[tot]=head[a];    head[a]=tot++;}void dfs(int u,int fa){    for(int i=head[u];i!=-1;i=next[i])    {        int vv=v[i];        if(vv!=fa)        {            dfs(vv,u);            for(int j=m;j>=0;j--)            {                //先将dp[vv][0]放进去，如果有更好的再将它替换，保证每组中都选一个                dp[u][j]+=dp[vv][0]+w[i]*2;                for(int k=1;k<=j;k++)                {                    dp[u][j]=min(dp[u][j],dp[u][j-k]+dp[vv][k]+k*w[i]);                }            }        }    }}int main(){    int n,s,a,b,c;    while(scanf("%d%d%d",&n,&s,&m)!=EOF)    {        tot=0;        memset(head,-1,sizeof(head));        memset(dp,0,sizeof(dp));        for(int i=1;i
     
    
   

 

转载地址：http://grddi.baihongyu.com/