題意：給你一顆樹有n個節點，樹的根節點為1，表示為敵人的基地，其他葉子節點為你的基地，你一開始有m元，給你每個節點可以建造的塔的數量和塔的價格和可以照成的傷害，每個節點至多建立一座塔。敵人的基地每次會派出一個敵人，他會去攻擊你的基地，但是你不能確定他會去攻擊哪一個基地，所以，請你計算出在花費不超過m的情況下，可以百分百消滅敵人的最大生命值（使得所有基地都免受攻擊）。
思路：樹上多組背包問題，dp方程有點難想，要取所有基地消滅生命值最小的最大值，還要注意塔花費為0的情況，具體見代碼。
代碼
#include<cstdio> #include<algorithm> using namespace std; const int maxn=1100; const int INF=0x3fffffff; int n,m,cnt; struct{int v,next; }edge[maxn*2]; int head[maxn]; struct{int pr,po; }nd[maxn][55];//記錄節點造塔的信息 int jc[maxn][220];//jc[i][j]表示在節點j上建塔花費j最大可以造成的傷害 int sz[maxn];//節點可以建塔的數量 int dp[maxn][220];//dp[i][j] 表示節點i花費j可以使得當前子樹的所有基地免受攻擊而消滅敵人的最大生命值 void add(int u,int v){edge[cnt].v=v;edge[cnt].next=head[u];head[u]=cnt++; } void dfs(int k,int fz){for(int i=0;i<=m;i++){dp[k][i]=INF;//因為找的是在保證所有基地不被攻擊下可以消滅的最大值生命值，所以先初始化為無窮大 jc[k][i]=0;//初始化 }for(int i=0;i<sz[k];i++){for(int j=nd[k][i].pr;j<=m;j++){jc[k][j]=max(jc[k][j],nd[k][i].po);//更新當前節點上建塔的信息 } }bool lg=true;//看是不是葉子節點 for(int i=head[k];i!=-1;i=edge[i].next){int v=edge[i].v;if(v!=fz){dfs(v,k);lg=false;for(int j=m;j>=0;j--){int mx=0; for(int j1=0;j1<=j;j1++){mx=max(mx,min(dp[k][j-j1],dp[v][j1]));//因為你不能確定選j1為多少時最大，所以不能直接用來更新dp[k][j] }dp[k][j]=min(dp[k][j],mx);// printf("ww%d %d %d %d\n",k,v,j,dp[k][j]); }// printf("\n"); }}if(lg){for(int i=0;i<=m;i++)dp[k][i]=jc[k][i];//在葉子節點時直接考慮在自己上面建塔 }else{for(int i=m;i>=0;i--){int mx=dp[k][i]; for(int j=0;j<=i;j++){//因為存在建塔的消耗為0的情況，當j==i時你在之前可能已經更新過dp[k][i]了，而再最后你又會 mx=max(mx,dp[k][j]+jc[k][i-j]);//用dp[k][i]和jc[k][0]來更新dp[k][i]，而你一個點只能建一座塔 ，所以用mx做過渡 //printf("%d %d %d %d %d %d %d\n",k,i,dp[k][i],j,dp[k][j],i-j,jc[k][i-j]); } dp[k][i]=mx;}// printf("\n"); } } int main(){int t;int u,v;scanf("%d",&t);while(t--){scanf("%d",&n);cnt=0;fill(head,head+2+n,-1);for(int i=1;i<n;i++){scanf("%d%d",&u,&v);add(u,v);add(v,u);}scanf("%d",&m);for(int i=1;i<=n;i++){scanf("%d",&sz[i]);for(int j=0;j<sz[i];j++){scanf("%d%d",&nd[i][j].pr,&nd[i][j].po);}}dfs(1,0);printf("%d\n",dp[1][m]);}return 0; }
?
