10.26 吃 Div.2 水分
10.26 Codeforces Round 982 (Div.2)
Solve : A~D2 (4/5)
Rank : 24
Rating : \(2098+114=2212\)
Pref : 2554 | 2520
发挥评价：Good-
果然还是 Div.2 善良啊！（）
随便做了前四道，没咋卡住，就这名次了，可惜 C 有一发罚时吃得不温不火。
然后 E1 咋这么难。
CF2027D1 / D2
长为 \(n\) 的序列 \(a\) 和长为 \(m\) 的不增序列 \(b\)，以及一个初始为 \(1\) 的变量 \(k\)。
每次可以做如下两件事情：
-
当 \(k<m\)，令 \(k\) 变为 \(k+1\)，花费为 \(0\)。
-
删除 \(a\) 的一段前缀，要求它的和小于 \(b_k\)，花费 \(m-k\)。
求删空的最小代价，D2 还要输出方案数。
由于 \(k\) 与删掉的前缀长度只增不减，考虑 \(dp_{i,j}\) 表示已经删除 \(i\) 个数，\(k=j\) 时的最小花费，答案为 \(dp_{n,k}\)。
然后发现删除得多肯定不劣，于是二分找到最长的能删除的前缀转移。
D2 要记录方案数，这下贪心转移直接坠机了。
考虑第一维枚举 \(j\)，然后发现每次转移形如给一段区间取 \(min\) 外加记录方案数，考虑标记永久化的线段树维护。