HDU 1011 Starship Troopers （樹形DP）

題目描述

傳送門

題目大意：有n個洞組成一棵樹，你有m個士兵，你從1号房間開始攻打，每個洞有a個”bugs”和b的價值。你的一個士兵可以打20個”bugs”，為了拿到這個洞的價值b你必須留下k個士兵消滅這個洞的所有”bugs”（k*20>=”bugs”的數量，且留下的士兵不可以再去攻打其他的洞，且必須攻打了前面的洞才可以攻打後面的洞）。問你花費這m個士兵可以得到的最大價值是多少。

題解

題解剛開始直接按照樹形依賴做的，就是讓每個子節點繼承上父親節點，再繼續DP

f[i][j+c[son]]=f[i][j]+val[son]

但是這樣做有一種情況不大好處理

5 2
0 1
0 1
0 5
0 1
0 2
1 2
1 3
2 4
2 5
           

每個點都沒有bug，也就是不需要士兵即可攻占。但是我們隻有兩個士兵，也就是隻能到達最多兩個葉子節點，是以這組資料的答案是9而不是10

我們用 f[i][j] 到達i，子樹中的花費是j的最大價值

f[x][j+k]=max(f[x][j+k],f[x][j]+f[son][k]) 注意k的最小值是1不是0，要不無法到達葉子節點，無法獲得這條路徑的代價。

這麼做的話需要特判m=0的情況，m=0,ans=0.

代碼

#include<cstdio>
#include<algorithm>
#include<cmath>
#include<cstring>
#include<iostream>
#define N 203
using namespace std;
int tot,point[N],nxt[N],v[N];
int c[N],val[N],dp[N][N],n,m;
void add(int x,int y)
{
    tot++; nxt[tot]=point[x]; point[x]=tot; v[tot]=y;
    tot++; nxt[tot]=point[y]; point[y]=tot; v[tot]=x;
}
void dfs(int x,int fa)
{
    /*if (x==1) dp[x][c[x]]=val[x];
    for (int i=point[x];i;i=nxt[i]) {
        if (fa==v[i]) continue;
        for (int j=0;j<=m;j++) 
         if (dp[x][j]) dp[v[i]][j+c[v[i]]]=dp[x][j]+val[v[i]];
        dfs(v[i],x);
        for (int j=0;j<=m;j++)
         dp[x][j]=max(dp[x][j],dp[v[i]][j]);
    }*/
    for (int i=c[x];i<=m;i++) dp[x][i]=val[x];
    for (int i=point[x];i;i=nxt[i]) {
        if (fa==v[i]) continue;
        dfs(v[i],x);
        for (int j=m;j>=c[x];j--)
         for (int k=;k+j<=m;k++)
          dp[x][j+k]=max(dp[x][j+k],dp[x][j]+dp[v[i]][k]);
    }
}
int main()
{
    freopen("a.in","r",stdin);
    freopen("my.out","w",stdout);
    while (true) {
        scanf("%d%d",&n,&m);
        if (n==-&&m==-) break;
        memset(dp,,sizeof(dp));
        for (int i=;i<=n;i++) {
            scanf("%d%d",&c[i],&val[i]);
            if (c[i]%) c[i]=c[i]/+;
            else c[i]=c[i]/;
        }
        tot=;
        memset(point,,sizeof(point));
        for (int i=;i<n;i++) {
            int x,y;scanf("%d%d",&x,&y);
            add(x,y);
        }
        if (m==) {
            printf("0\n");
            continue;
        }
        dfs(,);
        printf("%d\n",dp[][m]);
    }
}