- Gọi dp[i][j] là giá trị(danh tiếng) lớn nhất có thể tạo ra khi xét đến đỉnh i với tổng chi phí là j
=> Nếu tồn tại 1 cạnh u - v, ta có:
dp[u][i] = max(dp[u][i], dp[v][j] + dp[u][i - j])
__Đi theo công thức truy hồi, ta phải tính từ dưới lên bằng dfs__
__Ta không chọn "dp[v][j] + A[u][i - j]" vì chưa chắc giá trị mà u tạo ra đã hơn nhưng người trước đó"__
_Có thể khởi tạo dp[i][0 -> l] bằng cách nhập luôn để đỡ tốn thêm 1 mảng 2 chiều nữa..._
__ĐPT: O(n*max(S[u])*max(S[v]))__
__Code mẫu:__
#include <bits/stdc++.h>
using namespace std;
constexpr int mx = 5e2;
int n, l;
int dp[mx + 5][mx + 5];
int A[mx + 5][mx + 5];
int S[mx + 5];
vector<int> g[mx + 5];
void dfs(int u, int p){
for (int i = 0; i <= S[u]; ++i) dp[u][i] = A[u][i];
for (int v : g[u]){
if (v == p) continue;
dfs(v, u);
for (int i = S[u]; i >= 0; --i)
for (int j = 0; j <= min(i, S[v]); ++j)
dp[u][i] = max(dp[u][i], dp[v][j] + dp[u][i - j]);
}
}
int main(){
ios_base::sync_with_stdio(false);
cin.tie(NULL); cout.tie(NULL);
cin >> n >> l;
for (int u = 2; u <= n; ++u){
int v;
cin >> v;
g[u].push_back(v);
g[v].push_back(u);
}
for (int i = 1; i <= n; ++i) cin >> S[i];
for (int i = 1; i <= n; ++i)
for (int j = 0; j <= l; ++j) cin >> A[i][j];
dfs(1, 0);
int ans = 0;
for (int i = 0; i <= S[1]; ++i) ans = max(ans, dp[1][i]);
cout << ans;
}
Sherwin
Created at
1 likes