5 10 50 10 40 10 40 20 65 30 70 30 1 2 1 3 2 4 2 5 1 1 20 7 -1 -1
50 7
1 #include <iostream> 2 #include <cstdio> 3 #include <cstring> 4 #include <cmath> 5 #include <algorithm> 6 #include <climits> 7 #include <vector> 8 #include <queue> 9 #include <cstdlib> 10 #include <string> 11 #include <set> 12 #include <stack> 13 #define LL long long 14 #define INF 0x3f3f3f3f 15 using namespace std; 16 int n,m,bugs[110],p[110],dp[110][110]; 17 vector<int>g[110]; 18 void dfs(int u,int fa){ 19 int i,j,k; 20 for(i = bugs[u]; i <= m; i++) 21 dp[u][i] = p[u]; 22 for(i = 0; i < g[u].size(); i++){ 23 if(g[u][i] == fa) continue; 24 dfs(g[u][i],u); 25 for(j = m; j >= bugs[u]; j--){ 26 for(k = 1; k <= j-bugs[u]; k++){ 27 dp[u][j] = max(dp[u][j],dp[u][j-k]+dp[g[u][i]][k]); 28 } 29 } 30 } 31 } 32 int main(){ 33 int i,j,u,v; 34 while(scanf("%d %d",&n,&m),n != -1 && m != -1){ 35 for(i = 0; i <= n; i++) 36 g[i].clear(); 37 for(i = 1; i <= n; i++){ 38 scanf("%d %d",bugs+i,p+i); 39 bugs[i] = (bugs[i] + 19)/20; 40 } 41 memset(dp,0,sizeof(dp)); 42 for(i = 1; i < n; i++){ 43 scanf("%d %d",&u,&v); 44 g[u].push_back(v); 45 g[v].push_back(u); 46 } 47 if(m == 0) {puts("0");continue;} 48 dfs(1,-1); 49 cout<<dp[1][m]<<endl; 50 } 51 return 0; 52 }
BNUOJ 5235 Starship Troopers,布布扣,bubuko.com
原文:http://www.cnblogs.com/crackpotisback/p/3904331.html