三句话题解合集

P2837 [USACO08FEB]Dining Cows B

定义$pre_i$为将前$i$个数均改为1所需要的次数，$suf_i$同理，为后缀，但是为改成2所需的次数
然后遍历一边寻找答案即可
时间复杂度$O(n)$

P1020 导弹拦截

LIS 经典题，第一问为最长不升子序列长度，第二问为最长严格上升子序列长度
值域不大，不需要离散化，暴力BIT优化DP即可
时间复杂度$O(n log w)$，$w$为值域

P2642 双子序列最大和

最大子段和经典题，$pre_i$表示$a_1 - a_i$的最大子段和，$suf_i$为后缀，同理
暴力枚举断点统计答案即可
时间复杂度$O(n)$，记得开$\texttt{long long}$

P1982 小朋友的数字

用类似最大子段和的方式算出特征值，再扫一遍统计分数即可
需要写高精或者用$\texttt{int128}$，很毒瘤
时间复杂度$O(n)$

P1043 数字游戏

先考虑链上情况，定义$dp_{i,j}$为$a_1 - a_i$分成$j$段的极值，暴力枚举进行转移即可
环上问题做n次dp即可
时间复杂度$O(n^4)$

【LGR-075】1A/2C 「SWTR-6」GCDs & LCMs

对于两个正整数$a,b$，易得当$a<b,a+b+ \gcd(a,b)=\operatorname{lcm}(a,b)$时，$\frac{a}{b}=\frac{2}{3}$，证明略
强行dp，二分优化转移过程即可
时间复杂度$O(n log n)$

P4141 消失之物

背包经典题
先完成一遍背包进行预处理，在失去一个物品的时候反向转移减去它的贡献即可
时间复杂度$O(nm)$

CF366C Dima and Salad

简单推式子可得，题目求的是以$a_i-k*b_i$为大小，$a_i$为价值，背包大小为0时的方案数
分别用正数和负数进行一次背包即可
时间复杂度为$O(n^2w)$，其中$w$为值域

P4170 [CQOI2007]涂色

定义$dp_{i,j}$为将i~j之间的木板涂成正确颜色的最小代价
当$a_i=a_j$时，$dp_{i,j}=min(dp_{i,j-1},dp_{i+1,j})$
否则，$dp_{i,j}=min(dp_{i,k}+dp_{k+1,j}（i \leq k < j）$
简单进行转移即可，时间复杂度$O(n^3)$

P2851 [USACO06DEC]The Fewest Coins G

首先分别对于自己的硬币做多重背包，对于商家的硬币做完全背包
可以通过抽屉原理证得：商家所需要找的硬币面额不会超过$\max{V_i}^2$
需要注意的是，多重背包需要进行二进制优化。然后暴力枚举进行合并即可

CF1354D Multiset

对于这类的问题，首先考虑权值线段树或者平衡树
此题因为卡空间，因此只能使用权值线段树
对于1操作，直接线段树上二分并在节点上维护和即可
对于2操作，直接单点加即可
时间复杂度$O(q\log n)$，空间复杂度$O(4n)$

P3116 [USACO15JAN]Meeting Time S

根据题意可知本题的图为DAG，可以进行拓扑排序
定义$dp_{i,j}$表示能否恰好经过$j$的时间到达节点$i$，大力dp即可
分别对两个人做上面的dp，最后进行合并，时间复杂度$O(m \times\max\sum V_i)$，$V$为边权

P1330 封锁阳光大学

考虑对每个连通块进行二分图染色，并将两种颜色中点数少的那些点都放上河蟹
注意到，如果无法对某个连通块进行二分图染色，则答案为$\texttt{Impossible}$
大力bfs即可，时间复杂度$O(n+m)$

SP1437 PT07Z - Longest path in a tree

树直径板子
先以任意点为根做dfs，找到距离该节点最远的叶子
再以该点为根dfs，找到以它为根的树高，即为直径
时间复杂度$O(n)$

P2921 [USACO08DEC]Trick or Treat on the Farm G

注意到该题的图为基环内向树
大力topsort剪掉所有链上的点，再在剩余的环上暴力dfs统计答案，最后在反向图上dfs计算链上的点的答案
时间复杂度$O(n)$

P2661 信息传递

注意到该题的图为基环内向树
大力topsort剪掉所有链上的点，再暴力dfs寻找最小环即可
时间复杂度$O(n)$

CF1027D Mouse Hunt

注意到该题的图为基环内向树
大力topsort剪掉所有链上的点，再在剩余的环上暴力dfs统计最小点权即可
时间复杂度$O(n)$