软件开发专业能力,北京网站优化公司,搜索广告优化,公司网站建设的需求题意#xff1a;给你一颗树有n个节点#xff0c;树的根节点为1#xff0c;表示为敌人的基地#xff0c;其他叶子节点为你的基地#xff0c;你一开始有m元#xff0c;给你每个节点可以建造的塔的数量和塔的价格和可以照成的伤害#xff0c;每个节点至多建立一座塔。敌人的…题意给你一颗树有n个节点树的根节点为1表示为敌人的基地其他叶子节点为你的基地你一开始有m元给你每个节点可以建造的塔的数量和塔的价格和可以照成的伤害每个节点至多建立一座塔。敌人的基地每次会派出一个敌人他会去攻击你的基地但是你不能确定他会去攻击哪一个基地所以请你计算出在花费不超过m的情况下可以百分百消灭敌人的最大生命值使得所有基地都免受攻击。 思路树上多组背包问题dp方程有点难想要取所有基地消灭生命值最小的最大值还要注意塔花费为0的情况具体见代码。 代码 #includecstdio
#includealgorithm
using namespace std;
const int maxn1100;
const int INF0x3fffffff;
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].vv;edge[cnt].nexthead[u];head[u]cnt;
}
void dfs(int k,int fz){for(int i0;im;i){dp[k][i]INF;//因为找的是在保证所有基地不被攻击下可以消灭的最大值生命值所以先初始化为无穷大 jc[k][i]0;//初始化 }for(int i0;isz[k];i){for(int jnd[k][i].pr;jm;j){jc[k][j]max(jc[k][j],nd[k][i].po);//更新当前节点上建塔的信息 } }bool lgtrue;//看是不是叶子节点 for(int ihead[k];i!-1;iedge[i].next){int vedge[i].v;if(v!fz){dfs(v,k);lgfalse;for(int jm;j0;j--){int mx0; for(int j10;j1j;j1){mxmax(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 i0;im;i)dp[k][i]jc[k][i];//在叶子节点时直接考虑在自己上面建塔 }else{for(int im;i0;i--){int mxdp[k][i]; for(int j0;ji;j){//因为存在建塔的消耗为0的情况当ji时你在之前可能已经更新过dp[k][i]了而再最后你又会 mxmax(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);cnt0;fill(head,head2n,-1);for(int i1;in;i){scanf(%d%d,u,v);add(u,v);add(v,u);}scanf(%d,m);for(int i1;in;i){scanf(%d,sz[i]);for(int j0;jsz[i];j){scanf(%d%d,nd[i][j].pr,nd[i][j].po);}}dfs(1,0);printf(%d\n,dp[1][m]);}return 0;
} 转载于:https://www.cnblogs.com/cglongge/p/10526847.html
