Editorial for VM 08 Bài 26 - Đế chế hùng mạnh nhất
Remember to use this editorial only when stuck, and not to copy-paste code from it. Please be respectful to the problem author and editorialist.
Submitting an official solution before solving the problem yourself is a bannable offence.
Submitting an official solution before solving the problem yourself is a bannable offence.
Lưu ý: Các code mẫu dưới đây chỉ mang tính tham khảo và có thể không AC được bài tập này
Code mẫu của flashmt
uses math; const fi=''; maxn=100; maxm=2000; var n,m,re:longint; c,v:array[1..maxn] of longint; a:array[1..maxn,1..maxn] of boolean; f:array[1..maxn,0..maxm] of longint; procedure rf; var i,x,y:longint; begin read(n,m); for i:=2 to n do read(v[i]); for i:=2 to n do read(c[i]); for i:=1 to n-1 do begin read(x,y); a[x,y]:=true; a[y,x]:=true; end; end; procedure visit(x,cc,vv:longint); var i,j:longint; begin if cc>m then exit; for i:=1 to n do if a[x,i] then begin a[i,x]:=false; for j:=cc+c[i] to m do f[i,j]:=f[x,j-c[i]]+v[i]; visit(i,cc+c[i],vv+v[i]); for j:=cc+c[i] to m do f[x,j]:=max(f[x,j],f[i,j]); end; end; procedure pr; var j:longint; begin visit(1,0,0); for j:=0 to m do re:=max(re,f[1,j]); writeln(re); end; begin assign(input,fi); reset(input); rf; pr; close(input); end.
Code mẫu của ladpro98
#include <bits/stdc++.h> const int N = 110; const int M = 2020; using namespace std; int n, m, l, r; vector<int> a[N], child[N]; int Q[N], V[N], C[N], now[N]; bool was[N]; int* G[N][M]; void BFS() { l = 1, r = 1; int i, u, v; Q[1] = 1; was[1] = true; while (l <= r) { u = Q[l++]; for(int i = 0; i < a[u].size(); i++) { v = a[u][i]; if (!was[v]) { was[v] = true; child[u].push_back(v); Q[++r] = v; } } } } int DP(int u, int k) { if (now[u] >= k) return V[u] + G[u][k][child[u].size()]; int i, v; for(int money = now[u] + 1; money <= k; money++) { G[u][money] = new int[child[u].size() + 1]; G[u][money][0] = 0; for(i = 1; i <= child[u].size(); i++) { v = child[u][i - 1]; G[u][money][i] = G[u][money][i - 1]; for(int pay = money; pay >= C[v]; pay--) G[u][money][i] = max(G[u][money][i], G[u][money - pay][i - 1] + DP(v, pay - C[v])); } } now[u] = k; return V[u] + G[u][k][child[u].size()]; } int main() { scanf("%d %d", &n, &m); int i, j, u, v, sv = 0, sc = 0; for(i = 2; i <= n; i++) {scanf("%d", &V[i]); sv += V[i];} for(i = 2; i <= n; i++) {scanf("%d", &C[i]); sc += C[i];} if (m >= sc) {printf("%d", sv); return 0;} for(i = 1; i < n; i++) { scanf("%d %d", &u, &v); a[u].push_back(v); a[v].push_back(u); } BFS(); memset(now, 255, sizeof now); for(i = 1; i <= n; i++) { G[i][0] = new int[child[i].size()]; memset(G[i][0], 0, sizeof G[i][0]); } printf("%d", DP(1, m)); return 0; }
Code mẫu của RR
#include <iostream> #include <algorithm> #include <vector> #define FOR(i,a,b) for(int i=a; i<=b; i++) #define FORD(i,a,b) for(int i=a; i>=b; i--) #define FORV(i,v) for(typeof(v.begin()) i=v.begin(); i!=v.end(); i++) #define MAXN 111 #define PB push_back using namespace std; int debug=0; int n,m,value[MAXN],c[MAXN],f[MAXN][2011],g[MAXN][2011],visited[MAXN],sumc[MAXN]; vector<int> ke[MAXN]; void inp() { scanf("%d %d",&n,&m); FOR(i,2,n) scanf("%d",&value[i]); FOR(i,2,n) scanf("%d",&c[i]); FOR(i,2,n) { int u,v; scanf("%d %d",&u,&v); ke[u].PB(v); ke[v].PB(u); } } void dfs1(int u) { sumc[u]=c[u]; FORV(v,ke[u]) { if (sumc[*v]>=0) continue; dfs1(*v); sumc[u]+=sumc[*v]; } if (sumc[u]>m) sumc[u]=m; } void dfs2(int u) { visited[u]=1; f[u][0]=0; f[u][c[u]]=value[u]; g[u][0]=0; int now=0; FORV(v,ke[u]) { now++; if (visited[*v]) continue; dfs2(*v); FORD(p,sumc[u],0) FOR(tov,0,sumc[*v]) if (tov<=p) g[u][p] >?= f[*v][tov]+g[u][p-tov]; } FOR(p,c[u],sumc[u]) if (g[u][p-c[u]]) f[u][p] >?= value[u]+g[u][p-c[u]]; } void solve() { memset(sumc,-1,sizeof sumc); dfs1(1); if (debug) { FOR(i,1,n) cout<<sumc[i]<<" "; cout<<endl; } FOR(i,1,n) FOR(j,0,m) g[i][j]=f[i][j]=-1000111000; dfs2(1); if (debug) { FOR(i,1,n) { cout<<i<<": "; FOR(j,0,m) if (f[i][j]>=0) cout<<"("<<j<<","<<f[i][j]<<") "; cout<<endl; } } int res=0; FOR(i,0,m) res >?= f[1][i]; cout<<res; } int main() { // freopen("input.txt","r",stdin); // freopen("output.txt","w",stdout); inp(); solve(); return 0; }
Comments