首页 > 代码库 > HDU 1011 Starship Troopers(树形dp)
HDU 1011 Starship Troopers(树形dp)
OJ题目:click here~~
题目分析:一棵树,有n个结点 ,给每个结点的value 和 weight 。求容量为m的背包,能获得的最大value。选择了父结点才能选择子结点。m = 0时 ,输出0 , 即使有weight = 0 的结点,这是题目的一个trick。。
const int maxn = 102; int val[maxn]; int w[maxn]; vector<int> g[maxn]; int dp[maxn][maxn]; int n , m ; void dfs(int u , int father){ int v , i , j , k; for(i = w[u];i <= m;i++) dp[u][i] = val[u]; for(i = 0;i < g[u].size();i++){ v = g[u][i]; if(v == father) continue; dfs(v , u); for(j = m;j >= w[u];j--){ for(k = 1;k + j <= m;k++){ dp[u][j + k] = max(dp[u][j + k] , dp[v][k] + dp[u][j]); } } } } int main(){ int i , j , k ,a , b; //freopen("in.txt" , "r" , stdin); while(scanf("%d%d",&n,&m)){ if(n == -1 && m == -1) break; memset(dp , 0 , sizeof(dp)); for(i = 0 ;i <= n;i++) g[i].clear(); for(i = 1;i <= n;i++){ scanf("%d%d",&w[i] , &val[i]); w[i] = (w[i] + 19)/20;//计算每个结点需要的士兵数 } for(i = 1;i < n;i++){ scanf("%d%d", &a , &b); g[a].push_back(b); g[b].push_back(a); } if(m == 0) {puts("0") ; continue;}//没有士兵时,不能获得任何东西,即使有bug = 0的结点。 dfs(1 , -1); cout << dp[1][m] << endl; } }
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。