HDU 4003 樹形DP+背包

題意

給一棵樹，一堆機器人從根節點向下進行搜尋。要求搜尋到每個葉子節點，機器人可以向回走。問機器人行走最短總路徑和是多少。

題解

樹形DP+背包，不過不能算是嚴謹的背包。DP方程不太好想，dp[i][j]代表i點有j個機器人走了便不再回來。DP分兩步，第一步是假設所有的機器人走了以後都會回來，dp[s][j]+=dp[nd.to][0]+2*nd.val。第二步是派一部分機器人走下去便不用回來，dp[s][j]=min(dp[s][j],dp[s][j-q]+dp[nd.to][q]+q*nd.val)。這裡用到了類似滾動數組的東西，j一定要從k->0進行循環，對于每個位元組點的DP，我們可以選擇派出k->0個機器人，派出機器人以後針對這個節點便不需要派出機器人。是以dp[s][j-q]實際是通路完上一個節點及其子節點的費用，這樣加上這個節點派出方案的費用便是總費用。如果j從0->k進行循環，那麼便會重複針對這個點派出機器人，進而導緻機器人費用高于實際費用。這一點一定要想明白。

代碼

#include <iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<cmath>
#include<queue>
#include<string>
#include<set>
#include<map>
#include<bitset>
#include<stack>
#include<string>
#define UP(i,l,h) for(int i=l;i<h;i++)
#define DOWN(i,h,l) for(int i=h-1;i>=l;i--)
#define W(a) while(a)
#define MEM(a,b) memset(a,b,sizeof(a))
#define LL long long
#define INF 0x3f3f3f3f
#define MAXN 800010
#define MOD 1000000007
#define EPS 1e-3
using namespace std;

int dp[][];
int n,s,k;
struct Node{
    int to,val;

    Node(int to,int val):to(to),val(val){}
};

vector<Node> vc[];

void dfs(int s,int p)
{
        int sz=vc[s].size();
        UP(i,,sz){
            Node nd=vc[s][i];
            if(nd.to==p)
                continue;
            dfs(nd.to,s);
            DOWN(j,k+,){
                dp[s][j]+=dp[nd.to][]+*nd.val;
//                cout<<dp[s][j]<<endl;
                UP(q,,j+){
                    dp[s][j]=min(dp[s][j],dp[s][j-q]+dp[nd.to][q]+q*nd.val);
//                    cout<<"test"<<(dp[s][j-q]+dp[nd.to][q]+q*nd.val)<<" "<<s<<" "<<j<<endl;
                }
            }
        }
}

int main() {
    W(~scanf("%d%d%d",&n,&s,&k)){
        MEM(vc,);
        MEM(dp,);
        int a,b,w;
        UP(i,,n-){
            scanf("%d%d%d",&a,&b,&w);
            vc[a].push_back(Node(b,w));
            vc[b].push_back(Node(a,w));
        }
        dfs(s,-);
        int ans=INF;
        UP(i,,k+){
            ans=min(ans,dp[s][i]);
//            cout<<dp[s][i]<<endl;
        }
        printf("%d\n",ans);
    }
}