HDU 1561-The more, The Better（树状背包）

时间：2021-06-13 23:32:56

题意：

n个城堡，每个有一定的财富，有些城堡不能直接攻克，要攻克这些城堡必须先攻克其他某一个特定的城堡，求应攻克哪m个城堡，获得最大财富。

分析：dp[i][j]，以i为根的子树，攻克j个城堡，获得的最大财富，把0看做树的根节点

#include <map>

#include <set>

#include <list>

#include <cmath>

#include <queue>

#include <stack>

#include <cstdio>

#include <vector>

#include <string>

#include <cctype>

#include <complex>

#include <cassert>

#include <utility>

#include <cstring>

#include <cstdlib>

#include <iostream>

#include <algorithm>

using namespace std;

typedef pair<int,int> PII;

typedef long long ll;

#define lson l,m,rt<<1

#define pi acos(-1.0)

#define rson m+1,r,rt<<11

#define All 1,N,1

#define read freopen("in.txt", "r", stdin)

const ll  INFll = 0x3f3f3f3f3f3f3f3fLL;

const int INF= 0x7ffffff;

const int mod =  ;

vector<int>e[];

int dp[][],n,m;

void dfs(int root){

    for(int i=;i<e[root].size();++i){

        int son=e[root][i];

        dfs(son);

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

            for(int k=;k<j;++k)

            dp[root][j]=max(dp[root][j],dp[root][j-k]+dp[son][k]);

    }

}

int main()

{

    while(~scanf("%d%d",&n,&m)){

        if(n==&&m==)break;

        int a,b;

        memset(dp,,sizeof(dp));

        for(int i=;i<=n;++i)

            e[i].clear();

        for(int i=;i<=n;++i){

            scanf("%d%d",&a,&b);

            dp[i][]=b;

            e[a].push_back(i);

        }

        m++;

        dfs();

        printf("%d\n",dp[][m]);

    }

return ;

}

相关文章