10.26 Codeforces Round 982 (Div.2)

Solve : A~D2 (4/5)

Rank : 24

Rating : \(2098+114=2212\)

Pref : 2554

发挥评价：Good-

果然还是 Div.2 善良啊！（）

随便做了前四道，没咋卡住，就这名次了，可惜 C 有一发罚时吃得不温不火，比较可惜。

然后 E1 咋这么难。

CF2027D1 / D2

长为 \(n\) 的序列 \(a\) 和长为 \(m\) 的不增序列 \(b\)，以及一个初始为 \(1\) 的变量 \(k\)。

每次可以做如下两件事情：

1. 当 \(k<m\)，令 \(k\) 变为 \(k+1\)，花费为 \(0\)。

2. 删除 \(a\) 的一段前缀，要求它的和小于 \(b_k\)，花费 \(m-k\)。

求删空的最小代价，D2 还要输出方案数。

由于 \(k\) 与删掉的前缀长度只增不减，考虑 \(dp_{i,j}\) 表示已经删除 \(i\) 个数，\(k=j\) 时的最小花费，答案为 \(dp_{n,k}\)。

然后发现删除得多肯定不劣，于是二分找到最长的能删除的前缀转移。

D2 要记录方案数，这下贪心转移直接坠机了。

考虑第一维枚举 \(j\)，然后发现每次转移形如给一段区间取 \(min\) 外加记录方案数，考虑标记永久化的线段树维护。