http://acm.zju.edu.cn/onlinejudge/showProblem.do?problemCode=3201
树形DP,理解了其实很简单,一气呵成!!对于某个节点u,这个节点对于每个子节点都要更新一次,而且在更新时,子节点的信息已经递归的更新完成了。在更新完某一个子节点之后,此时的dp[u]就包含了之前更新的子节点的信息了。(如果之前不知道肯定不知道我在说什么TAT)还要注意的一点就是,针对某个子节点v更新的时候,我们需要的dp[u]是更新v之前的dp值,因此需要逆序更新。。这其实也很好理解。最后分析一下效率,没个子节点更新一次,与边数对应,因此共更新n-1次,没次更新都是n*n,那么总共的效率是
O(n^3)。
#include<cstdio>
#include<algorithm>
#include<string.h>
#include<vector>
using namespace std;
vector<int> adj[105];
int n,ss,w[105],dp[105][105];
void solve(int u,int fa)
{
int size=adj[u].size();
dp[u][1]=w[u];
for(int i=0;i<size;++i)
{
int v=adj[u][i];
if(v==fa)
continue;
solve(v,u);
for(int j=n;j>=2;--j)
{
for(int k=1;k<=j;++k)
{
dp[u][j]=max(dp[u][j],dp[u][k]+dp[v][j-k]);
}
}
}
}
int main()
{
while(scanf("%d %d",&n,&ss)!=EOF)
{
memset(adj,0,sizeof(adj));
memset(dp,0,sizeof(dp));
for(int i=0;i<n;++i)
scanf("%d",&w[i]);
for(int i=0;i<n-1;++i)
{
int u,v;
scanf("%d %d",&u,&v);
adj[u].push_back(v);
adj[v].push_back(u);
}
solve(0,-1);
int res=0;
for(int i=0;i<n;++i)
res=max(res,dp[i][ss]);
printf("%d\n",res);
}
}
分享到:
相关推荐
最近在acm.zju.edu.cn上通过的题目的代码,都是比较有价值的题目
zoj吐血制作,希望大家喜欢
zoj网站中多个练习的c++解答,文件名即为题目序号。经本人测试可以使用,主要为动态规划方面的问题,希望给初学者提供帮助。
这是一份ZOJ的ACM题解,包含大多数题目的AC程序,是学习算法的好东西~
zoj在线评测系统前台和后台源代码,包括比赛用的客户端源代码
ZOJ 1055 Oh, Those Achin Feet.bfs求最短路径.
zoj4041正确题解源代码,以及运行程序
acm中zoj1002的可运行C++程序
浙江大学ZOJ源码题解,按照题目类型和难易分类。
一个非常非常非常非常实用的zoj结题代码
问题:枫教授在一所大学教数学,他发现了一个函数,用于获得一个表达式的操作数的目的,函数命名op(i,e)可以描述如下:
zoj的代码实现,很好,而且很全面,全部实现。
zoj_1004.cpp 求单词字母进出栈后能形成目标串的进出方案 广度优先搜索求解
ZOJ上的一些水题,4.16浙江省程序设计竞赛的题目
zoj 2536 这个不是用贪心做的
zoj上的3607Lazier Salesgirl AC代码及一些注释。贪心算法
浙大acm OJ1204,自己做的,已经AC 分享一下,若有更好的算法可以教教我
能AC 通过的c++代码,包括zoj1002,1091,1789
浙江大学zoj题目代码,大量水题代码,齐全
ZOJ解题报告ZOJ解题报告ZOJ解题报告ZOJ解题报告