P1273有线电视网

继续肝dp
这是一道很简单的树上背包
理解思想后不难
代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
const int maxn = 3005;
const int inf = (1 << 30) - 1;
int n,m;
int val[maxn];
int dp[maxn][maxn];
struct Edge{
int u,v,w;
Edge(int u,int v,int w):u(u),v(v),w(w){}
};
vector<Edge> G[maxn];
int dfs(int u){
if(u>n-m){
dp[u][1]=val[u];
return 1;
}
int sum=0;
for(int i=0;i<G[u].size();i++){
Edge &e=G[u][i];
int t=dfs(e.v);
sum+=t;
for (int j = sum; j > 0;j--){
for (int k = 1; k <= t;k++){
if(j-k>=0){
dp[u][j] = max(dp[u][j], dp[u][j - k] + dp[e.v][k] - e.w);
}
}
}
}
return sum;
}
int main(){
cin>>n>>m;
for (int i = 1;i<=n-m;i++){
int t;
cin>>t;
for(int j=0;j<t;j++){
int v,w;
cin>>v>>w;
G[i].push_back(Edge(i, v, w));
}
}
for (int i = n - m + 1; i <= n;i++){
cin >> val[i];
}
for (int i = 0; i <= n;i++){
for (int j = 0; j <= n;j++){
dp[i][j] = -inf;
}
}
for(int i=1;i<=n;i++){
dp[i][0] = 0;
}
dfs(1);
// for (int i = 1;i<=n;i++){
// cout << dp[1][i] << " ";
// }
//cout << endl;
for (int i = n; i >= 1; i--)
{
if (dp[1][i] >= 0)
{
cout << i;
return 0;
}
}
}