首页 技术 正文
技术 2022年11月23日
0 收藏 511 点赞 2,462 浏览 2519 个字

因为苹果可能在不同的子树中,所以,很容易想到设状态dp_back[i][j]为以i点为树根走j步并回到i点的最大苹果数与dp_to[i][j]不回到i点的两个状态。

于是,转移方程就很明显了。只是注意要减去一来一回,或者不回的边。树形DP里套背包。

但这题远比这复杂,个人认为。因为在实现上细节太多。

实现代码1:

 #include <iostream>
#include <cstdio>
#include <vector>
using namespace std; const int MAX=;
vector<int>G[MAX];
int num[MAX],dp_back[MAX][MAX*],dp_to[MAX][MAX*];
int tback[MAX*],tto[MAX*];
int n,s; void init(){
for(int i=;i<=n;i++)
G[i].clear();
memset(dp_back,,sizeof(dp_back));
memset(dp_to,,sizeof(dp_to));
} void dfs(int u,int f){
int size=G[u].size();
for(int i=;i<size;i++){
int v=G[u][i];
if(v!=f){
dfs(v,u);
for(int p=;p<=s;p++){
tback[p]=dp_back[u][p];
tto[p]=dp_to[u][p];
for(int k=;k<=p;k++){
if(p-k->=){
tback[p]=max(tback[p],dp_back[u][p-k-]+dp_back[v][k]+num[v]);
}
if(p-k->=){
tto[p]=max(tto[p],dp_back[u][p-k-]+dp_to[v][k]+num[v]);
}
if(p-k->=){
tto[p]=max(tto[p],dp_to[u][p-k-]+dp_back[v][k]+num[v]);
}
}
}
for(int j=;j<=s;j++){
dp_back[u][j]=tback[j];
dp_to[u][j]=tto[j];
}
}
}
} int main(){
int u,v;
while(scanf("%d%d",&n,&s)!=EOF){
init();
for(int i=;i<=n;i++)
scanf("%d",&num[i]);
for(int i=;i<n;i++){
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(,);
int ans=max(dp_to[][s],dp_back[][s]);
ans+=num[];
printf("%d\n",ans);
}
return ;
}

这是我WA了N久后看了别人的改过来的,每次在DP时才把根节点的值加上。说不清为什么,但是对了。

另一个是我原本WA的代码,可以把OJ的讨论板所有数据都过了,但依然WA,后来研究了好久,发现自己代码上的一个问题,那就是当最大步数超过边数的两倍时,就会出现问

题,于是,我只好投机一点,最后扫描一次结果值来获得正确值了。

 #include <iostream>
#include <cstdio>
#include <vector>
using namespace std; const int MAX=;
vector<int>G[MAX];
int num[MAX],dp_back[MAX][MAX*],dp_to[MAX][MAX*];
int tback[MAX*],tto[MAX*];
int n,s; void init(){
for(int i=;i<=n;i++)
G[i].clear();
memset(dp_back,,sizeof(dp_back));
memset(dp_to,,sizeof(dp_to));
} void dfs(int u,int f){
int size=G[u].size();
dp_back[u][]=num[u];
dp_to[u][]=num[u];
for(int i=;i<size;i++){
int v=G[u][i];
if(v!=f){
dfs(v,u);
for(int p=;p<=s;p++){
tback[p]=dp_back[u][p];
tto[p]=dp_to[u][p];
for(int k=;k<=p;k++){
if(p-k->=){
tback[p]=max(tback[p],dp_back[u][p-k-]+dp_back[v][k]);
}
if(p-k->=){
tto[p]=max(tto[p],dp_back[u][p-k-]+dp_to[v][k]);
}
if(p-k->=){
tto[p]=max(tto[p],dp_to[u][p-k-]+dp_back[v][k]);
}
}
}
for(int j=;j<=s;j++){
dp_back[u][j]=tback[j];
dp_to[u][j]=tto[j];
}
}
}
} int main(){
int u,v;
while(scanf("%d%d",&n,&s)!=EOF){
init();
for(int i=;i<=n;i++)
scanf("%d",&num[i]);
for(int i=;i<n;i++){
scanf("%d%d",&u,&v);
G[u].push_back(v);
G[v].push_back(u);
}
dfs(,);
// int ans=max(dp_to[1][s],dp_back[1][s]);
// ans+=num[1];
int ans=;
for(int i=;i<=s;i++)
ans=max(ans,max(dp_back[][i],dp_to[][i]));
printf("%d\n",ans);
}
return ;
}

两个代码除了初始化的位置不一样,其他都是一样的。但我感觉代码2更符合本来的转移方程,你看一下初始化的位置就明白。但最终问题时,不能处理好,那就是当最大步数超过边数的两倍时问题,因为我在初始化时就认为这是一种不可能的情况了。。。

所以,请路过大牛给指点,以去掉最后的扫描一次得到结果。。。

微信扫一扫

支付宝扫一扫

本文网址:https://www.zhankr.net/141080.html

相关推荐
python开发_常用的python模块及安装方法
adodb:我们领导推荐的数据库连接组件bsddb3:BerkeleyDB的连接组件Cheetah-1.0:我比较喜欢这个版本的cheeta…
日期:2022-11-24 点赞:878 阅读:7,097
Educational Codeforces Round 11 C. Hard Process 二分
C. Hard Process题目连接:http://www.codeforces.com/contest/660/problem/CDes…
日期:2022-11-24 点赞:807 阅读:4,454
下载Ubuntn 17.04 内核源代码
zengkefu@server1:/usr/src$ uname -aLinux server1 4.10.0-19-generic #21…
日期:2022-11-24 点赞:566 阅读:5,265
可用Active Desktop Calendar V7.86 注册码序列号
可用Active Desktop Calendar V7.86 注册码序列号Name: www.greendown.cn Code: &nb…
日期:2022-11-24 点赞:733 阅读:5,147
Android调用系统相机、自定义相机、处理大图片
Android调用系统相机和自定义相机实例本博文主要是介绍了android上使用相机进行拍照并显示的两种方式,并且由于涉及到要把拍到的照片显…
日期:2022-11-24 点赞:512 阅读:6,314
Struts的使用
一、Struts2的获取  Struts的官方网站为:http://struts.apache.org/  下载完Struts2的jar包,…
日期:2022-11-24 点赞:671 阅读:3,859