xp04 - day06 考试
2025-08-18 09:19:56
发布于：浙江
48阅读
0回复
0点赞
医院设置
#include <bits/stdc++.h>
using namespace std;
int n, w[5005], d[5005], ans = 2e9, vis[5005];
vector <int> g[5005];
int check(){
int sum = 0;
for (int i = 1; i <= n; i++) sum += d[i] * w[i];
return sum;
}
void dfs (int fa){
vis[fa] = 1;
for (int son : g[fa]){
if (!vis[son]){
d[son] = d[fa] + 1;
dfs (son);
}
}
}
int main(){
cin >> n;
for (int i = 1; i <= n; i++) cin >> w[i];
for (int i = 1; i <= n; i++){
int u, v;
cin >> u >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1; i <= n; i++){
memset (vis, 0, sizeof vis);
memset (d, 0, sizeof d);
dfs(i);
ans = min(ans, check());
}
cout << ans;
return 0;
}
知识闯关大冒险
#include<bits/stdc++.h>
using namespace std;
const int N = 100010;
int dp[N],a[N];
int main() {
int n;
cin >> n;
for(int i = 1; i <= n; i++) cin >> a[i];
dp[0] = 0;
dp[1] = a[1];
for(int i = 2; i <= n; i++) {
dp[i] = max(dp[i-1],dp[i-2]+a[i]);
}
cout<<dp[n];
return 0;
}
树上慈善
\#include <bits/stdc++.h>
using namespace std;
const int N = 6010;
int n;
vector<int> tr[N];
long long dp[N][2],a[N];
void dfs(int u,int fa){
dp[u][1] = a[u];
dp[u][0] = 0;
for(int son:tr[u]){
if(son==fa)continue;
dfs(son,u);
dp[u][0] += max(dp[son][0],dp[son][1]);
dp[u][1] += dp[son][0];
}
}
int main() {
cin >> n;
for (int i = 1; i <= n; i++) cin>>a[i];
for (int i = 1; i <= n - 1; i++) {
int a, b;
cin >> a >> b;
tr[a].push_back(b);
tr[b].push_back(a);
}
dfs(1, -1);
cout<<max(dp[1][0],dp[1][1]);
return 0;
}
二叉苹果树
#include <bits/stdc++.h>
using namespace std;
const int N = 110;
int n,m;
struct node{
int y,w;
};
vector<node> tr[N];
long long dp[N][N];//以u为根的子树中花了 x 个树枝留下的最多苹果数量
void dfs(int u,int fa){
for(node now:tr[u]){
int son = now.y,w = now.w;
if(son==fa)continue;
dfs(son,u);
for(int j=m;j>=0;j--){
for(int k=j-1;k>=0;k--){
dp[u][j] = max(dp[u][j-1-k]+dp[son][k]+w,dp[u][j]);
}
}
}
}
int main() {
cin >> n >> m;//树枝
for (int i = 1; i <= n - 1; i++) {
int a, b, c;
cin >> a >> b >> c;
tr[a].push_back({b,c});
tr[b].push_back({a,c});
}
dfs(1, -1);
cout<<dp[1][m];
return 0;
}
有帮助，赞一个