标签：总结 code max 线段 模拟 maxl 集合 终章 dp

2024.10.30

T1 追逐游戏 (chase)

被自己的分讨绕死了，以后要学会简化

code

T2 统计

code

T3 软件工程

选前\(k - 1\)长的 + 剩下求交集可得\(96\) ~~为什么我贪的不对qwq ~~

把这个贪心改成大炮就是整洁的一部分

定义\(dp_{i,j}\)表示前\(i\)条线段放到\(j\)个集合里，那么上述方法就是

\[dp_{i,j} = max(dp_{i - 1,j},dp_{i - 1,j - 1} + len_i) \]

这个只适用于存在不交的线段，此时把它们扔到一个集合里都没贡献

那么剩余情况就要对当前线段分是否独占一个集合来转移了

\[dp_{i,j} = max(dp_{i - 1,j - 1} + len_i,dp_{i - 1,j} - max(0,l - maxl)) \]

其中\(maxl\)是之前集合的交集，这样子放损耗最小

code

T4 命运的X

code

标签：总结,code,max,线段,模拟,maxl,集合,终章,dp
From： https://www.cnblogs.com/MLP123/p/18516508