今日偶然打开 \(oi-wiki\)，发现树形 \(DP\) 例题正好是之前在洛谷上鸽着的一道题。所以......
\(\color{red}{很高兴以这样的方式认识你，树形 DP !}\)
这例题造的太好了，简直是无痛入门（感动.jpg）
\(dp_i\) 表示的是以 \(i\) 为根节点的子树所获得的最大价值。
由于每个节点代表着一位人物，有来与不来两种状态，所以再加一维状态变量。
\(dp_{i,0}\) 表示以 \(i\) 为根节点的子树所能获得的最大价值，且这位人物没来。 \(dp_{i,1}\) 则对应来了的状态。
现在有个周年庆宴会，宴会每邀请来一个职员都会增加一定的快乐指数 r_i。
但是呢，如果某个职员的直接上司来参加舞会了，那么这个职员就无论如何也不肯来参加舞会了。
根据题意描述，容易得出状态转移方程：
\(dp_{i,0} += max (dp_{j,0},dp_{j,1})\)
\(dp_{i,1} += dp_{j,0}\)
\(j\) 指的是 \(i\) 的子节点，且显然 \(dp_{i,1}\) 的初始值为 \(r_i\)。
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,a[6005];
int head[6005],nex[6005],edge[6005],tot;
int vis[6005],dp[6005][2];
void dfs(int x){
dp[x][1]=a[x];
for(int i=head[x];i;i=nex[i]){
int y=edge[i];
dfs(y);
dp[x][1]+=dp[y][0];
dp[x][0]+=max(dp[y][0],dp[y][1]);
}
return;
}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<n;i++){
int l,k;
scanf("%d%d",&l,&k);
nex[++tot]=head[k];
head[k]=tot;
edge[tot]=l;
vis[l]=1;
}
for(int i=1;i<=n;i++){
if(!vis[i]){
dfs(i);
cout<<max(dp[i][0],dp[i][1])<<endl;
return 0;
}
}
}
由于这题是无向图（但由于以 \(n-1\) 条边相连接，所以本质与树并无太大区别），所以要讨论以谁作为根节点。
根节点之所以重要，是因为在递归过程中，我们已经默认根节点所代表的那束花已经被保留了，但根节点代表的花不一定在最优解的集合之中。
仔细模拟后，不难发现，对于以 \(i\) 为根节点的子树，\(dp_i\) 往下为最优解，而往上由于还未更新，因此相当于剪去 \(dp_i\) 与其根节点的枝桠。
进一步推理，无论通过哪个节点作为根节点，再递归的过程中，其实已经变相枚举了将其剪去的种种情况，所以，只需要在过程中取最优解即可。
这点比较好理解，所以合并在一起阐述。
\(dp_i\) 表示以 \(i\) 为根节点的子树所获得的最大美丽值。
显然有
\(dp_i+=max(dp_j,0)\)。
\(j\) 为子节点，当其所带来的价值为负数时，不如直接剪掉。
有几处雷点在注释中标记出来了（都是血泪教训啊QAQ）
#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,ans=-0x3f3f3f3f;//答案可能为负！要初始化为负无穷
int head[16005],nex[35005],edge[35005],tot;//由于是双向边，所以空间要开双倍
int dp[16005],vis[16005];
void dfs(int x){
vis[x]=1;//不要在循环内标记，否则标记不到根节点本身。
for(int i=head[x];i;i=nex[i]){
int y=edge[i];
if(vis[y]) continue;
dfs(y);
if(dp[y]<=0) continue;
dp[x]+=dp[y];
}
ans=max(ans,dp[x]);
return;
}
void add(int l,int k) {nex[++tot]=head[k],head[k]=tot,edge[tot]=l;}
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&dp[i]);
for(int i=1;i<n;i++){
int l,k;
scanf("%d%d",&l,&k);
add(l,k);
add(k,l);
}
dfs(1);
cout<<ans<<endl;
return 0;
}
第 \(7、8\) 道，(‾◡◝)。
加油！
我好像记得Lua有类似Ruby的method_missing的东西。还是我记错了？ 最佳答案 表的metatable的__index和__newindex可以用于与Ruby的method_missing相同的效果。 关于ruby-难道Lua没有和Ruby的method_missing相媲美的东西吗？，我们在StackOverflow上找到一个类似的问题： https://stackoverflow.com/questions/7732154/
我有一个奇怪的问题:我在rvm上安装了rubyonrails。一切正常，我可以创建项目。但是在我输入“railsnew”时重新启动后，我有“程序'rails'当前未安装。”。SystemUbuntu12.04ruby-v"1.9.3p194"gemlistactionmailer(3.2.5)actionpack(3.2.5)activemodel(3.2.5)activerecord(3.2.5)activeresource(3.2.5)activesupport(3.2.5)arel(3.0.2)builder(3.0.0)bundler(1.1.4)coffee-rails(
我想在一个没有Sass引擎的类中使用Sass颜色函数。我已经在项目中使用了sassgem，所以我认为搭载会像以下一样简单:classRectangleincludeSass::Script::FunctionsdefcolorSass::Script::Color.new([0x82,0x39,0x06])enddefrender#hamlengineexecutedwithcontextofself#sothatwithintemlateicouldcall#%stop{offset:'0%',stop:{color:lighten(color)}}endend更新:参见上面的#re
大家好!我想知道Ruby中未使用语法ClassName.method_name调用的方法是如何工作的。我头脑中的一些是puts、print、gets、chomp。可以在不使用点运算符的情况下调用这些方法。为什么是这样？他们来自哪里？我怎样才能看到这些方法的完整列表？ 最佳答案 Kernel中的所有方法都可用于Object类的所有对象或从Object派生的任何类。您可以使用Kernel.instance_methods列出它们。 关于没有类的Ruby方法？，我们在StackOverflow
我真的为这个而疯狂。我一直在搜索答案并尝试我找到的所有内容，包括相关问题和stackoverflow上的答案，但仍然无法正常工作。我正在使用嵌套资源，但无法使表单正常工作。我总是遇到错误，例如没有路线匹配[PUT]"/galleries/1/photos"表格在这里:/galleries/1/photos/1/edit路线.rbresources:galleriesdoresources:photosendresources:galleriesresources:photos照片Controller.rbdefnew@gallery=Gallery.find(params[:galle
我在Rails应用程序中使用CarrierWave/Fog将视频上传到AmazonS3。有没有办法判断上传的进度，让我可以显示上传进度如何？ 最佳答案 CarrierWave和Fog本身没有这种功能；你需要一个前端uploader来显示进度。当我不得不解决这个问题时，我使用了jQueryfileupload因为我的堆栈中已经有jQuery。甚至还有apostonCarrierWaveintegration因此您只需按照那里的说明操作即可获得适用于您的应用的进度条。 关于ruby-on-r
如何在Ruby中获取BasicObject实例的类名？例如，假设我有这个:classMyObjectSystem我怎样才能使这段代码成功？编辑:我发现Object的实例方法class被定义为returnrb_class_real(CLASS_OF(obj));。有什么方法可以从Ruby中使用它？ 最佳答案 我花了一些时间研究irb并想出了这个:classBasicObjectdefclassklass=class这将为任何从BasicObject继承的对象提供一个#class您可以调用的方法。编辑评论中要求的进一步解释:假设你有对象
目录前言滤波电路科普主要分类实际情况单位的概念常用评价参数函数型滤波器简单分析滤波电路构成低通滤波器RC低通滤波器RL低通滤波器高通滤波器RC高通滤波器RL高通滤波器部分摘自《LC滤波器设计与制作》，侵权删。前言最近需要学习放大电路和滤波电路，但是由于只在之前做音乐频谱分析仪的时候简单了解过一点点运放，所以也是相当从零开始学习了。滤波电路科普主要分类滤波器：主要是从不同频率的成分中提取出特定频率的信号。有源滤波器：由RC元件与运算放大器组成的滤波器。可滤除某一次或多次谐波，最普通易于采用的无源滤波器结构是将电感与电容串联，可对主要次谐波（3、5、7）构成低阻抗旁路。无源滤波器：无源滤波器，又称
我在非Rails项目中使用ActiveRecord。在Rails中，我可以这样做:config.time_zone='EasternTime(US&Canada)'config.active_record.default_timezone='EasternTime(US&Canada)'但如果我不使用rails，我该如何设置时区？ 最佳答案 ActiveRecord::Base.default_timezone='EasternTime(US&Canada)' 关于ruby-没有轨道的A
@作者:SYFStrive @博客首页:HomePage📜：微信小程序📌：个人社区（欢迎大佬们加入）👉：社区链接🔗📌：觉得文章不错可以点点关注👉：专栏连接🔗💃：感谢支持,学累了可以先看小段由小胖给大家带来的街舞👉微信小程序（🔥）目录自定义组件-behaviors 1、什么是behaviors 2、behaviors的工作方式 3、创建behavior 4、导入并使用behavior 5、behavior中所有可用的节点 6、同名字段的覆盖和组合规则总结最后自定义组件-behaviors 1、什么是behaviorsbehaviors是小程序中，用于实现