社区讨论

如果您 90 分且样例没过

P4362[NOI2002] 贪吃的九头龙参与者 1已保存回复 0

讨论操作

快速查看讨论及其快照的属性,并进行相关操作。

当前回复
0 条
当前快照
1 份
快照标识符
@lzqpftyw
此快照首次捕获于
2024/08/12 16:01
2 年前
此快照最后确认于
2024/08/12 16:49
2 年前
查看原帖
这个题目如果按照普通的树性背包来考虑,直接倒序枚举,就会出错,原因就是没有考虑 m=2m = 2fu,0,0f_{u, 0, 0} 的处理。
m=2m = 2 时,fu,0,0f_{u, 0, 0} 应该为子树内所有边的边权之和,因为整个子树不准分配给最大的那个头,那就只能由另外一个头全部吃掉了,这时所有的边的两个端点都是由同一个头吃掉的。
而我们理所当然地认为 fu,0,0=0f_{u, 0, 0} = 0,这就导致了错误,以至于后面的所有状态的更新都是错误的。
这也是为什么临时树组赋值无穷大以后不会再初始化 tmp0,0tmp_{0, 0}tmp1,1tmp_{1, 1} 的原因。

回复

0 条回复,欢迎继续交流。

正在加载回复...