1889C
CF1889C2 Doremy's Drying Plan (Hard Version)
Problem - C2 - Codeforces Doremy's Drying Plan (Hard Version) - 洛谷 很好的一道 \(dp\) 题,无论是 \(dp\) 状态还是优化都很思维 我们设 \(dp_{i,j}\) 表示考虑了前 \(i\) 个城市,第 \(i\) 个城市干 ......
《CF1889C2 Doremy's Drying Plan (Hard Version)》 解题报告
考场上不会做。 如果考虑删掉哪些区间实际上不太可做。正难则反,转化贡献,考虑哪些点可以有贡献。 显然一个点如果可能有贡献,那么当且仅当覆盖它的区间 \(\le K\) 个。 于是我们记一个状态 \(f_{i,j}\) 表示前 \(i\) 个点中, \(i\) 是最后一个贡献的点,已经删除了 \(j\ ......