由于不是求最大的可拦截的HP值，而是要将最小值最大化，那么就需要分配每个子树用的钱数以达到最小值最大化
第一步解决如何分配钱使得结点u的子树中用了j元钱后可以拦截的HP最大，这就是变形的分组（依赖）背包，即枚举m元钱，在子树v用t元钱，在v之前的子树用j-t元钱
用Max[v][j]数组记录u的前v个结点花j元钱可以拦截的最大HP，Max[v][j]=max{min( dp[v][t] , Max[v-i][j-t] )},第一维v可以压缩掉
第二步考虑结点u上建立什么炮塔，用Max数组来求出dp[u][j]即可
/* 给定一棵树，m块钱，每个结点上可以建造k种(价格price，攻击力power)防御塔 求可以阻拦的最大血量 dp[i][j]表示子树i中花费j元可以抵挡的怪物血量 */ #include<bits/stdc++.h> using namespace std; #define maxn 1050 struct Edge{int to,nxt;}edge[maxn<<2]; struct node{int k,price[100],power[100];}p[maxn]; int n,m,head[maxn],tot,dp[maxn][210],flag[maxn]; void init(){ tot=0; memset(head,-1,sizeof head); memset(flag,0,sizeof flag); } void addedge(int u,int v){ edge[tot].to=v;edge[tot].nxt=head[u];head[u]=tot++; } void dfs(int u,int pre){ //init,每个点只能建立一个塔嘛 for(int j=m;j>=0;j--) for(int i=1;i<=p[u].k;i++) if(j>=p[u].price[i]) dp[u][j]=max(dp[u][j],p[u].power[i]); if(flag[u]==1&&u!=1)return;//叶子节点退出 for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i].to; if(v!=pre)dfs(v,u); } //Max[i][j]表示给前i个儿子花费j元时可以拦截的最大hp，可压成滚动数组 int Max[210]; memset(Max,0x3f,sizeof Max); for(int i=head[u];i!=-1;i=edge[i].nxt){ int v=edge[i].to; if(v==pre)continue; for(int j=m;j>=0;j--){//给子树v之前的子树用j元 int maxx=0; for(int t=0;t<=j;t++)//给子树v用t元 maxx=max(maxx,min(dp[v][t],Max[j-t]));//找出最优的分配方式 Max[j]=maxx;//记录 } } //最后Max数组表示给u的子树总共花i元可以拦截的最大HP for(int j=m;j>=0;j--) for(int t=0;t<=j;t++)//给子树花费t，给自己花费j-t元 dp[u][j]=max(dp[u][j],dp[u][j-t]+Max[t]); //printf("%d\n",u); //for(int i=1;i<=m;i++) // printf("%d ",dp[1][i]); } int main(){ int t,u,v; cin>>t; while(t--){ init(); scanf("%d",&n); for(int i=1;i<n;i++){ scanf("%d%d",&u,&v); addedge(u,v); addedge(v,u); flag[u]++;flag[v]++; } scanf("%d",&m); for(int i=1;i<=n;i++){ scanf("%d",&p[i].k); for(int j=1;j<=p[i].k;j++) scanf("%d%d",&p[i].price[j],&p[i].power[j]); } memset(dp,0,sizeof dp); dfs(1,0); printf("%d\n",dp[1][m]); } }
转载于:https://www.cnblogs.com/zsben991126/p/10348262.html
