hdu4044GeoDefense 树形dp+分组背包
分类：dp
dp
;const int maxn = 1010;const int inf = 0x7fffffff ;int dp[maxn][maxn] ;vector<int> vec[maxn] ;int c[maxn][maxn] , v[maxn][maxn] ,len[maxn] ;int tmp[maxn] ;int vis[maxn] ;int n , m ;void debug(){for(int i = 1;i <= n;i++)for(int j = 0;j <= m;j++)printf(“%d%c” ,dp[i][j] , j == m ?’\n’:’ ‘);}void dfs(int u){int flag = 0 ;for(int i = 0;i < vec[u].size() ;i++){int v = vec[u][i] ;if(vis[v])continue ;vis[v] = 1;dfs(v) ;if(flag == 0){for(int j = 0;j <= m;j++)dp[u][j] = dp[v][j] ;flag = 1 ;}elsefor(int j = m;j >= 0;j–){int temp = 0 ;for(int k = 0;k <= j;k++)temp = max(temp , min(dp[v][k] , dp[u][j-k])) ;dp[u][j] = temp ;}}for(int i = 0;i <= m;i++)tmp[i] = dp[u][i] ;//处理price为0的情况for(int j = m;j >= 0;j–)for(int i = 1;i <= len[u] ;i++)if(j < c[u][i])continue ;else dp[u][j] = max(dp[u][j] , tmp[j-c[u][i]]+ v[u][i]) ;}int main(){//freopen(“in.txt” ,”r” ,stdin) ;int t;scanf(“%d” ,&t) ;while(t–){scanf(“%d” ,&n) ;for(int i = 1;i <= n;i++)vec[i].clear();memset(len , 0 , sizeof(len)) ;for(int i = 1;i < n;i++){int a , b;scanf(“%d%d” ,&a , &b) ;vec[a].push_back(b) ;vec[b].push_back(a) ;}scanf(“%d” ,&m) ;for(int i = 1;i <= n;i++){scanf(“%d” ,&len[i]) ;for(int j = 1;j <= len[i] ;j++)scanf(“%d%d” ,&c[i][j] ,&v[i][j]) ;}memset(vis , 0 ,sizeof(vis)) ;memset(dp , 0 , sizeof(dp)) ;vis[1] = 1;dfs(1) ;cout<<dp[1][m]<<endl;}return 0 ;}/*131 32 1402 0 20 0 102 10 20 30 402 30 50 50 30*/
版权声明：本文为博主原创文章，，未经博主允许不得转载。
上一篇hdu1712ACboy needs your help 分组背包模板题下一篇hdu3450Counting Sequences 树状数组
顶0踩0
而只有在充满了艰辛的人生旅途中，始终调整好自己观风景的心态，
