打卡信奥刷题（2877）用C++实现信奥题 P5054 [COCI 2017/2018 #7] Dostavljač

P5054 [COCI 2017/2018 #7] Dostavljač

题目描述

自从 Krešo 开始种植辣椒以来，克罗地亚各地的 $N$ 家餐馆都对他的辣椒感兴趣，因此他们可以用真正的香料来丰富他们的菜肴。由于需求量很大，Krešo 决定开始作为辣椒的送货员。

餐馆用从 $1$ 到 $N$ 的数字表示，并且与 $N-1$ 个道路相互连接，使得可以在任何两个餐馆之间旅行。Krešo 在 $1$ 号餐厅开始他的旅程。在一个单位的时间里，他可以开车到相邻的餐厅或将辣椒送到现在的餐馆。对于每家餐厅，我们都知道所需的辣椒数量 $A_i$。

由于交付货物很累，Krešo 决定在交付和旅行上花费总共 $M$ 个单位的时间，之后他计划休息一下。

确定 Krešo 在给定时间范围内可以提供的最大辣椒数量。你可以假设 Krešo 总是带有无限量的辣椒。

输入格式

第一行输入包含两个整数 $N$ 和 $M$（$1\le N,M\le 500$），餐馆数量和 Krešo 计划用于交付辣椒的时间。

第二行输入包含 $N$ 个整数 $A_i$（$1\le A_i\le 10^6$），用 $i$ 表示的餐馆所需的辣椒数量（$1\le i\le N$）。

以下 $N-1$ 行中的每一行包含两个整数 $U$ 和 $V$（$1\le U,V\le N$，$U\ne V$），其表示餐馆 $U$ 和 $V$ 之间的道路。

输出格式

您必须输出 Krešo 在给定时间范围内可以提供的最大量的辣椒。

输入输出样例 #1

输入 #1

3 5
9 2 5
1 2
1 3

输出 #1

14

输入输出样例 #2

输入 #2

4 5
1 1 1 2
1 2
2 3
3 4

输出 #2

3

输入输出样例 #3

输入 #3

5 10
1 3 5 2 4
5 2
3 1
2 3
4 2

输出 #3

15

C++实现

#include <bits/stdc++.h>
#define int long long
using namespace std;
const int N=505;
int f[N][N][2],n,m,w[N];
vector <int> a[N];
void dfs(int u,int fa) {
for(int v:a[u]) {
if(v==fa) continue ;
dfs(v,u);
for(int i=m;i>=0;i—) {
for(int j=m;j>=0;j—) {
if(i+j+2<=m) {
f[u][i+j+2][0]=max(f[u][i+j+2][0],f[u][i][0]+f[v][j][1]);
f[u][i+j+2][1]=max(f[u][i+j+2][1],f[u][i][1]+f[v][j][1]);
}
if(i+j+1<=m) f[u][i+j+1][0]=max(f[u][i+j+1][0],f[u][i][1]+f[v][j][0]);
}
}
}
}
signed main() {
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
cin>>n>>m;
for(int i=1;i<=n;i++) {
cin>>w[i];
for(int j=1;j<=m;j++) f[i][j][1]=w[i];
for(int j=1;j<=m;j++) f[i][j][0]=w[i];
}
for(int i=1;i<n;i++) {
int u,v;
cin>>u>>v;
a[u].push_back(v);
a[v].push_back(u);
}
dfs(1,0);
cout<<max(f[1][m][1],f[1][m][0]);
return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容