专栏文章

P5521 [yLOI2019] 梅深不见冬 题解

XX_X_M
题解参与者 1已保存评论 0

文章操作

快速查看文章及其快照的属性，并进行相关操作。

当前评论
0 条
当前快照
1 份
快照标识符
@miqde78c
此快照首次捕获于
2025/12/04 02:58
3 个月前
此快照最后确认于
2025/12/04 02:58
3 个月前
查看原文

Step1 脑补fusu的行走过程，建立模型：

记对于 ii 节点的答案为 did_i，思考 did_i 的意义为行走的“任意时刻”场面上梅花数量的最大值。
我们希望建立从叶子节点向根递推的关系。由此，不妨先考虑简单一些的初始情况：
当节点为叶子节点时，di=wid_i=w_i。
当节点的孩子全都是叶子节点时:
我们记 SiS_i 为节点 ii 的孩子集合，则：
di=wi+∑j∈Siwjd_i=w_i+\sum_{j\in S_i}w_j。
那么，上述式子是否对于所有节点都成立？思考反例，答案是否定的。
事实上，在fusu行走的过程中，我们在孩子 jj 的子树中放置 djd_j 朵梅花时：
场面中的梅花数量= djd_j ++ 在之前走过的孩子节点中放置的梅花数量
综上，我们有如下的递推关系：
di=max⁡{maxj∈Sr(dj+∑early(k,j)wk),wi+∑j∈Siwj}d_i=\max\{max_{j\in S_r}(d_j+\sum_{early(k,j)}w_k),w_i+\sum_{j\in S_i}w_j\}
其中拜访节点的序列是任意的，我们可以自己决定。

Step2 确定正确序列服从的贪心关系

所有孩子节点具有的数值为 dj,wjd_j,w_j，它们的任意性很强，唯一具有的特点为 dj≥wjd_j\geq w_j。
把上面那个玩意揪出来，我们希望最小化的是：
maxj∈Sr(dj+∑early(k,j)wk)max_{j\in S_r}(d_j+\sum_{early(k,j)}w_k)
不妨先取例测试，这里我取的是：
i)i)
{(dj,wj)}=(1,1),(2,2),(3,3),(4,4)\{(d_j,w_j)\}=(1,1),(2,2),(3,3),(4,4)
调整这些数对的顺序，我们发现无论怎样调整，答案都是 1+2+3+4=101+2+3+4=10。
ii)ii)
{(dj,wj)}=(1,0),(2,1),(3,2),(4,3.5)\{(d_j,w_j)\}=(1,0),(2,1),(3,2),(4,3.5)
严格意义上，这里取 0,3.50,3.5 是不规范的，但可以将 00 视作一个无穷小量，并同时将它们放大。
注意到最优的序列之一为：
(1,0),(3,2),(2,1),(4,3.5)(1,0),(3,2),(2,1),(4,3.5)
运气很好，介于此及 dd 和 ww 的大小关系，可以猜想最优序列按照 d−wd-w 的数值随拜访次序递减。

Step3 复杂度分析+优化

遍历一遍树的复杂度： O(n)O(n)
孩子节点排序的总复杂度： O(nlogn)O(nlogn)，因为每个孩子节点都仅考虑一遍。
足以通过本题。

Step4 Coding

以下是主要代码：
CPP


bool cmp(node2 x,node2 y){
	return (x.d-x.w)>(y.d-y.w);
}

void dfs(int u){
	int cnt2=0;
	for(int j=head[u];j!=0;j=edge[j].nxt){
		int v=edge[j].v;
		dfs(v);
		d[u]+=w[v];
	}
	d[u]+=w[u];
	for(int j=head[u];j!=0;j=edge[j].nxt){
		int v=edge[j].v;
		c[cnt2].w=w[v];
		c[cnt2].d=d[v];
		cnt2++;
	}
	if(cnt2==0){
		return;
	}
	sort(c,c+cnt2,cmp);
	int sumw=0;
	for(int i=0;i<cnt2;i++){
		d[u]=max(d[u],sumw+c[i].d);
		sumw+=c[i].w;
	}
}

评论

共 0 条评论，欢迎与作者交流。

正在加载评论...