HDU 1561 树形DP(入门)
2024-09-28 23:18:41
题目链接: HDU 1561 The more, The Better
#include <iostream>
#include <cstdio>
#include <cmath>
#include <cstdlib>
#include <string>
#include <cstring>
#include <algorithm>
#include <iomanip>
#include <vector> using namespace std;
const int inf = 0x7FFFFFFF;
const int maxn = 1000000;
vector<int>V[205]; int n,m;
int dp[205][205];
bool vis[205]; void Init(){
for(int i=0;i<=n;++i)
V[i].clear();
memset(dp,0,sizeof(dp));
memset(vis,false,sizeof(vis));
for(int i=0; i<=n; ++i)
for(int j=2; j<=m; ++j)
dp[i][j]=-1;
} void DFS(int cnt){
vis[cnt]=true;
int len=V[cnt].size();
for(int i=0;i<len;++i){
int next=V[cnt][i];
if(!vis[next]) DFS(next);
for(int j=m;j>=2;--j)
for(int k=1;k<j;++k)
if(dp[next][j-k]!=-1&&dp[cnt][k]!=-1)
dp[cnt][j]=max(dp[cnt][j],dp[next][j-k]+dp[cnt][k]);
}
} int main(){
while(~scanf("%d%d",&n,&m),n+m){
Init();
for(int i=1;i<=n;++i){
int a,b;
scanf("%d%d",&a,&b);
dp[i][1]=b;
V[a].push_back(i); /// a的子结点
}
++m;
DFS(0);
printf("%d\n",dp[0][m]);
}
return 0;
}
最新文章
- ASP.NET、JAVA跨服务器远程上传文件(图片)的相关解决方案整合
- mybatis研究:select性能对比
- 微软connect教程系列&mdash;EntityFramework7(三)
- Spring MVC 学习总结(一)——MVC概要与环境配置
- Make Blog Beautiful
- JS构造函数的用法和JS原型
- POJ 1305 Fermat vs. Pythagoras (毕达哥拉斯三元组)
- hdu 4462(状态压缩)
- DedeCms 5.7友情链接模块注入漏洞
- [Python]豆瓣用户读书短评下载工具
- ubuntu10.10 tftp安装,配置,测试
- HDU 4513 哥几个系列故事——形成完善II manacher求最长回文
- Java DB loadBalance 设计
- 发短信utils
- 分布式系统之消息中间件rabbitmq
- 【BZOJ1059】【ZJOI2007】矩阵游戏
- SQL Server 增加链接服务器
- win10安装JDK详细教程
- SpringMVC-2-(Controller)
- Volley使用