可能更好的阅读体验 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 )。然后记得别见祖宗。
代码：
P3431
前情提要：本题视频 link 的一定提示下。
42PTS 做法：
显然简单 dp 一下即可，不多讲了，复杂度 O(n×m)\mathcal{O}(n \times m)O(n×m)。
60PTS 做法
不难发现我们原本的转移代码是：
dpi,j=max(dpi−1,j,dpi,j−1)+w[i]dp_{i,j}=\max(dp_{i-1,j},dp_{i,j-1})+w[i] dpi,j =max(dpi−1,j ,dpi,j−1 )+w[i]
由于数组存不下，我们不妨转换下。定义 dpidp_idpi 为起点到第 iii 个点的最大值。我们发现地图里有很多滚木，所以我们只需要存有人的点即可。不难发现，这个点只能从他“左上方位”的点更新。则方程变为：
若有 i≠j,xj≤xi,yj≤yxi≠j,x_j \le x_i,y_j \le y_xi=j,xj ≤xi ,yj ≤yx ，则
dpi=dpj+widp_i=dp_j+w_i dpi =dpj +wi
其中 jjj 为符合以上条件的权值最大的点。
那不行啊，还是很难维护，那咋办。
看看能不能降下来一维，可以把 xxx 升序排序，所有 yyy 在当 xxx 相等的情况下升序排列，这样就可以减掉 xxx 的那个维度，接下来只用维护 yyy 就可以了。
转移方程变为：
满足 j<i,yj≤yij<i,y_j \le y_ij<i,yj ≤yi ，则
dpi=dpj+wjdp_i=dp_j+w_j dpi =dpj +wj
一样的，jjj 为所有满足以上条件的 dpdpdp 数组的最大值下标。
复杂度相较以前有了很大改善，为 O(k2)\mathcal{O}(k^2)O(k2)。
正解
你知道的，这题是数据结构优化 DP。
看看用什么优化。
发现对于更新 dpidp_idpi ，dp1...i−1dp_{1...i-1}dp1...i−1 肯定都被更新过了。转化一下，我们需要一个数据结构来维护 111 到 i−1i-1i−1 最大的值，也就是维护 yyy。区间查询单点修改，显然 BIT 码量与常数最小，可以胜任。那么在原代码基础上加上 BIT 维护即可。记得离散化。
代码：
时间复杂度 O(klogk)\mathcal{O}(k \log k)O(klogk)。
这道题或许可以算是我独立做的，看视频发现这道题，之后开始打部分分。40pts40pts40pts 的代码做完之后有事走了。路上一直在想方法，想到了 60pts60pts60pts 的做法。吃饭的时候想到了 100pts100pts100pts 的做法。在做之前看了一部分的视频，但我没看懂你信吗（
