可能更好的阅读体验 link，优先更新这里
受到 AIerqwq and wcqwqk 的启发，打算写个题解记录做过的题。以下题目会先用口胡的形式呈现（注意不保证解法正确），后续可能会加上代码 and 正确思路。也欢迎各位大佬来指正我的口胡思路 awa。
部分题目出自题单：https://www.luogu.com.cn/training/9350
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
P1095
本来写的是贪心，但这个做法会写成构式大分讨，还是老老实实写 DP 吧。
移动有三个优先级：
1. 直接魔法移动
2. 恢复魔法值后魔法移动
3. 跑步
不难发现，使用跑步的情况，要么是充能时间足够跑出去，要么就是剩余时间不足以进行第二轮充能。
定义 dpidp_idpi 为第 iii 秒所能移动到的最远距离。先按照上述优先级构建好 dpdpdp 数组。第二轮我们考虑可以在恢复魔法值时间内里开的情况，把所有休息替换成奔跑。如果到了终点直接输出即可。
代码(排班有点小问题，不用在意)：
------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------------
P1462
开始是不会做的，看了下 tag 有一丢丢思路了。
发现题目要求经过城市单次交费最大值的最小值，考虑二分答案。其中的 check 函数就是最短路，如果可以跑完，那就往大了跑，否则就往小了跑。
代码：
咕咕咕
B4133
诶我咋跑过来做橙题了。
定义 dpidp_idpi 为从 111 到 iii 的最大字段和，显然转移方程为 dpi=max(dp[i−1]+a[i],a[i])dp_i=\max(dp[i-1]+a[i],a[i])dpi =max(dp[i−1]+a[i],a[i])。答案为 max(a1,a2...an)\max(a_1,a_2...a_n)max(a1 ,a2 ...an )。
代码：
P1439
乍一看 LCS，仔细一看确实 LCS。居然是绿题 /yiw。
不怼，这个数据怎么高达 10510^5105。
不管了先写部分分。
50%50\%50% 部分分
显然为朴素 LCS。定义 dpi,jdp_{i,j}dpi,j 为长度分别是 i,ji,ji,j 两串的 LCS。若 ai=aja_i=a_jai =aj 则 dpi,j=dpi−1,j−1+1dp_{i,j}=dp_{i-1,j-1}+1dpi,j =dpi−1,j−1 +1。否则 dpi,j=max(dpi−1,j,dpi,j−1)dp_{i,j}=\max(dp_{i-1,j},dp_{i,j-1})dpi,j =max(dpi−1,j ,dpi,j−1 )。那么代码易得。
代码（我是码风切换大佬 awa）：
诶那你就要问了，100100100 分咋弄啊。这你就问对人了，我会用最直白，最不绕弯子的方式告诉你，我不会（。至少目前不会，满分做法请参考题解 awa
P1507
诶这不是 01 背包板子吗。
哦不对，要维护体积和质量两个参数。
考虑让 dpj,kdp_{j,k}dpj,k 维护质量，体积分别为 j,kj,kj,k 情况下所能取到的最大价值。转移方程为 dpj,k=max(dpj,k,dpj−W[i],k−V[i]+v[i])dp_{j,k}=\max(dp_{j,k},dp_{j-W[i],k-V[i]}+v[i])dpj,k =max(dpj,k ,dpj−W[i],k−V[i] +v[i])。其中 W,V,vW,V,vW,V,v 分别为物品的质量，体积与卡路里。
代码：
P3379
学的是 Tarjan 求 LCA。板子就不多讲了。
（雷霆码风
B3694
离散板子，但我为啥没做。
P14920
啥意思啊，这都是黄吗。
诶不是咋只有 60 pts。哦 kkk 有 10910^9109
那咋办。
转化一下，变成求提升攻击力所需要的最小金币数，只要这个值小于 kkk 即可直接输出。转移方程变为 dpj=min(dpj,dpj−ai+ci)dp_j=\min(dp_j,dp_{j-a_i}+c_i)dpj =min(dpj ,dpj−ai +ci )。然后记得别见祖宗。
代码：
