三句话题解_1

· · 个人记录

盼望着，盼望着，十一月来了，NOIP的脚步近了

1.P7077 [CSP-S2020] 函数调用

我们观察到，我们可以把答案的贡献拆成 a_i*mul+add_i。

从后往前处理，记录乘法标记，加法乘上当前乘法标记 (75 pts)。

将乘法视为多次调用加法，建出函数调用 DAG ，拓扑排序计算答案 (100pts)。

鲜花：所以这题哪里用dp了？

qwq

2.P3953 [NOIP2017 提高组] 逛公园

观察到 K 很小 ，考虑 O(nk) 的dp (记搜)

正着dij一遍，倒着算当前路径与最短路的偏移量

注意考虑0环，多测清空

lovol

3[P6820 [PA2012] Two Cakes(https://www.luogu.com.cn/problem/P6820)

写出n方dp方程，考虑优化

发现可以设 dp_i 表示 AB两个序列都写到i的ans

边界特殊处理