题目要求共有n个结点,将其中k个点染成黑色(本题解中为了方便描述,通称所有未染色的点为白点),求黑点两两距离及白点两两距离,使他们之和最大。 我们可以将距离转化为路径,然后再将路径拆分成边,就可以记录每条边被经过的次数,直接计算即可。 问题来了!:那么每条边会对答案贡献多少呢? 我们不妨设这条边的一侧共有w个点,其中有t个点被染成黑色了; 那么这一侧共有t个黑点,(w-t)个白点;类似,另一侧有(k-t)个黑点,(n-w-k+t)个白点; 令sz为这条边的边权,那么贡献就是val=sz*(t*(k-t)+(w-t)*(n-w-k+t)); 解题的大致思路就是计算每条边对答案的贡献,最后利用状态转移方程求出最优解。 首先给出状态数组:f[x][y]; f[x][y]表示给以x为根结点的子树染上y个点所得的对于整棵树的最大贡献;
方程如下: f[i][j]=max(f[i][j],f[i][j-t]+f[z][t]+val);(z表示i的子结点) 目标状态:f[1][k]; 最后附上代码 PS:中间可能遇到非法情况,建议把f[x][y]预处理成非法情况,方便跳过处理(代码最后有针对这点的样例,可自行调试); 强烈建议参考代码理解!!!!! Over. (第一次写题解,不足之处请大家多多包涵》_《)
题目1962 [HAOI 2015]树上染色
AAAAAAAAAA
5
评论
2022-03-01 19:52:22
|
|
题目3449 [USACO Feb06]特殊津贴
AAAAAAAAAA
3
评论
2021-12-22 21:40:34
|
|
Pro1697 人工湖 题解•【题目描述】 有一个湖,他的周围都是城市,每个城市都只和他相邻的两个城市有道路相连。假设有n个城市,编号1-n,公路是双向的,公路有时候是好的,有时候是坏的,现在询问你两个城市是否可以互相到达。 •【输入格式】 第一行两个数,一个2<=n<=100000 和 1<=m<=100000,分别代表城市数目和询问次数; 接下来m行,每一行三个数f,a,b。f=0时,如果公路a,b之间的道路之前是好的,现在就变成坏的,如果之前是坏的,现在就变成好的。f=1时,询问a,b两个城市是否可以互相到达。 •【输出格式】 对于每一个f=1的询问,能到达输出“YES”,否则输出"NO". 思路如下: 首先,我们可以设g[x]数组表示x号城市与x+1号城市之间的道路好坏情况:g[x]=1时表示坏,g[x]=0时表示好,同时设sz为坏的道路的个数。 因为所有城市围起来形成一个圆,规定x到(x+1)号城市为顺时针方向,x到(x-1)号城市为逆时针方向。 我们来谈谈f=1时,即判断a、b两城市是否可以到达(预处理使a<b)。 那么在判断a、b两城市是否可以到达时,我们只需考虑两种情况: (1):沿顺时针道路判断是否可以到达 令G=g[a]+g[a+1]+g[a+2]+……+g[b-1](即a沿顺时针到b间的路径间坏的道路的个数)很明显,我们只需判断G是否>=1。若是,则表示a沿顺时针到b之间的路径有坏的道路,不能从a顺时针到达b。 (2):沿逆时针道路判断是否可以到达 其实思路也不难想出,我们可以简单地处理出sz(即坏的道路的个数),若sz-G=0, 即表示除a沿顺时针到b的路径间坏的道路外,没有坏的道路,这就等同于a沿逆时针到b的路径间没有坏的道路,可以从a到b。 反之(sz-G不为0)则表示a沿逆时针到b之间的路径有坏的道路,不能从a顺时针到达b。
好了,现在你已经了解了这题的大致思路了,那么就尝试AC吧!!!(不是 以上思路大家肯定都想到了(所以以上都是废话),那么我们开始优化时间吧! 我们懂得,若按照以上思路暴力求解,那么时间复杂度为O(nm),只能拿到50pts 接下来考虑100pts算法 我们可以发现g是一维数组,求G为g的区间求和,那么很自然的就联想到树状数组 设树状数组f[x]表示坏的道路的个数, G=g[a]+g[a+1]+g[a+2]+…… +g[b-1] =求和f(b-1)-求和f(a-1) 然后1与n号城市间的道路做个特殊处理。 最后推荐大家参考代码理解(COGS代码已开放) Over!!!
题目1697 人工湖
AAAAAAAAAA
3
评论
2021-12-22 21:37:57
|
|
裸裸的区间DP。 我们定义f[l][r] 为卖掉l到r之间的临时得到的最大收益。 n[x]为第x个物品的价值。 Cl为第几天出售 转移方程就应该是f[l][r]=max(f[l+1][r]+cl*n[l],f[l][r+1]+cl*n[r]); 最后附上代码)
题目3449 [USACO Feb06]特殊津贴
AAAAAAAAAA
3
评论
2021-12-22 21:26:17
|