<address id="rf17h"><dfn id="rf17h"></dfn></address>
    <address id="rf17h"><var id="rf17h"></var></address> <sub id="rf17h"><var id="rf17h"><ins id="rf17h"></ins></var></sub><address id="rf17h"></address>

    <address id="rf17h"><listing id="rf17h"><ins id="rf17h"></ins></listing></address>

    <sub id="rf17h"><var id="rf17h"></var></sub>
    <sub id="rf17h"><var id="rf17h"><output id="rf17h"></output></var></sub>

      <address id="rf17h"></address>
      <sub id="rf17h"><var id="rf17h"></var></sub>
          <sub id="rf17h"><dfn id="rf17h"><ins id="rf17h"></ins></dfn></sub>

          hdoj4276(树形dp+分组背包)

          题目链接:https://vjudge.net/problem/HDU-4276

          题意:给出一棵树,起点为1,时间为V,终点为n,每个点有一个价值a[u],每条边有一个时间花费w,求在时间V内到达终点n可以获得的最大价值。

          思路:

            考虑边有两种情况,一种是属于1->n路径上的(只用走一次),一种是不属于该路径上的(需要走两次),为了统一,不妨把V减去1-n路径上的权值和,然后把1->n路径上边的权值置为0。

            此时就转换为求在起点1,在时间V内回到起点的最大价值。用dp[u][j]表示在点u有时间j,最后回到点u的最大价值,dp[u][j]初始化为a[u](0<=j<=V),转移方程为:
              dp[u][j]=max(dp[u][j],dp[u][j-tmp-k]+dp[v][k]。

            其中v为u的子结点,tmp=2×w(u,v)。

          AC代码:

          #include<cstdio>
          #include<algorithm>
          #include<cstring>
          using namespace std;
          
          int n,V,a[105],e[105][105],dp1[105],dp2[105][505];
          
          void dfs1(int u,int fa){
              dp1[u]=-1;
              if(u==n) dp1[u]=0;
              for(int i=1;i<=n;++i)
                  if(e[u][i]!=-1){
                      if(i==fa) continue;
                      dfs1(i,u);
                      if(dp1[i]!=-1){
                          dp1[u]=dp1[i]+e[u][i];
                          e[u][i]=e[i][u]=0;
                      }
                  }
          }
          
          void dfs2(int u,int fa){
              for(int j=0;j<=V;++j)
                  dp2[u][j]=a[u];
              for(int i=1;i<=n;++i)
                  if(e[u][i]!=-1){
                      if(i==fa) continue;
                      dfs2(i,u);
                      int tmp=2*e[u][i];
                      for(int j=V;j>=tmp;--j)
                          for(int k=0;k<=j-tmp;++k)
                              dp2[u][j]=max(dp2[u][j],dp2[u][j-tmp-k]+dp2[i][k]);
                  }
          }
          
          int main(){
              while(~scanf("%d%d",&n,&V)){
                  for(int i=1;i<=n;++i)
                      for(int j=1;j<=n;++j)
                          e[i][j]=-1;
                  for(int i=1;i<n;++i){
                      int u,v,w;
                      scanf("%d%d%d",&u,&v,&w);
                      e[u][v]=e[v][u]=w;
                  }
                  for(int i=1;i<=n;++i)
                      scanf("%d",&a[i]);
                  dfs1(1,0);
                  if(V<dp1[1]){
                      printf("Human beings die in pursuit of wealth, and birds die in pursuit of food!\n");
                      continue;
                  }
                  V-=dp1[1];
                  dfs2(1,0);
                  printf("%d\n",dp2[1][V]);
              }
              return 0;
          }
          相关文章
          相关标签/搜索
          王中王中特免费公开资料选料 噶尔县| 祁阳县| 革吉县| 肇州县| 新乐市| 顺义区| 双江| 雅安市| 稻城县| 汝州市| 搜索| 仁化县| 镶黄旗| 湖北省| 聂拉木县| 鄂伦春自治旗| 五河县| 定兴县| 清流县| 虞城县| 浏阳市| 湖北省| 怀宁县| 隆德县| 和平县| 区。| 周至县| 德兴市| 东宁县| 西安市| 磐石市| 曲周县| 北海市| 西昌市| 高清| 常州市| 德化县| http://fa.hz0j0r5vo.fun http://fa.hz0j1r8vo.fun http://fa.hz0j0r7vo.fun http://fa.hz0j1r4vo.fun http://fa.hz0j0r6vo.fun