HDU 1561-The more, The Better(树状背包)
2024-08-25 05:20:22
题意:
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 ;
}
最新文章
- Windows下用python编写简单GUI程序的方法
- Thread.Sleep in WinRT
- servlet的生命周期与运行时的线程模型
- Python可变参数
- Informatica Powercenter学习笔记
- Java虚拟机工作原理详解 ( 二 )
- AVG()和to_date()函数的使用
- UVa 11582 (快速幂取模) Colossal Fibonacci Numbers!
- IOS - IOS之同步请求、异步请求、GET请求、POST请求
- 【Unity编程】四元数(Quaternion)与欧拉角
- 【POJ】2115 C Looooops(扩欧)
- nginx部署~dotnetCore+mvc网站502
- Gradle打jar包命令
- 启动fiddler导致浏览器无法上网的解决方法
- mysql数据库卸载和安装
- Centos yum国内源及配置含义
- C++重载操作符自增自减
- C++学习(一)之Visual Studio安装以及首次使用
- python查找字符串 函数find() 用法
- 【jQuery】jquery.metadata.js验证失效