为了补上我dp的短板（其实说真的dp约等于没学过，板都没有的那种），也为了以后复习dp不会再忘记dp怎么写，dp的各种思想是怎么来的，从零开始学习 dp ，并记录在此博客。
当然也会记录日常生活
大概是首发于洛谷博客，可能会同步到博客园，以后搭了个人blog就会同步到个人blog。
于 2023.11.23 22:00
今日写了 洛谷题单 - 动态规划的引入 思维导图里的题
虽然是基础题，但基础不牢，地动山摇，更何况我是真的有题不会（没错就是基础题不会）
$ $
纸币问题1：没什么好讲的我都写的出 要用一些不同面值的纸币凑出一个金额，每种纸币无数张，问最少用多少张可凑出。
如果要求最少使用张数，我们可以知道最后这个金额肯定是要从前面某个金额的最小使用张数+1而来，那么就可以从1枚举到最后金额，求出每个金额的最小使用张数一个个转移就是。
$ $
数字三角形：这是真的没什么好讲的了。
$ $
纸币问题2：不讲题面了
题目说了顺序不同也算一种方案，那么我们就可以从1转移到最后金额，当前金额方案数等于前面所有可以通过加上某个面值后等于当前金额的金额的方案数的和
$ $
现在顺序不同不能算贡献了，考虑外层枚举面额，内层枚举1到w的金额，\(dp_{i,j}\) ，表示算到第 i 个面额，金额 j 有多少个方案，因为面值个数是作数的，所以从当前面额扫到 w ，这样就可以看作是一个面额算了多次，因为 dp 数组只跟 i-1 ，即上一层有关系，所以可以滚掉 i 这一维，贴一下关键代码：
for (int i = 1; i <= n; i++)
for (int j = val[i]; j <= w; j++)
dp[j] =(dp[j]+ dp[j - val[i]])%MOD;
$ $
采药：每个物品有一个花费和一个贡献值，要求总花费小于 T 的情况下最大化贡献。
考虑每一个物品，设 \(dp_{i,j}\)，表示限制选前 i 个物品在总花费为 j 时的最大值，我们知道在同一区间内物品可提供价值是一样的，所以不用考虑最后花费为不到 T 的情况。接着就可以写出转移方程 \(dp_{i,j}=\max(dp_{i,j},dp_{i-1,j-cost_i}+val_i)\) 表示在选前 i-1 个物品当前总花费 j 减去这个物品的花费后最大的贡献是多少，再加上当前物品的贡献，与自身取个 max 就可以得到自身的最大值，这里采用记搜的思路会更好理解一点
我们发现 \(dp_{i,j}\) 只和 i-1 有关，可以滚掉 i 这一维，其实做了这题后，我终于理解了为什么有些转移是从后向前有些是从前向后，重点在于滚掉一维后，按某种顺序会影响到后面求值，而不是像二维那样可以不用管，当然这只是其中之一，还有就是本身求值就是和当前物品前面的求值挂钩的要按特定顺序。而且滚掉一维实际上是有常数优化的，如果有时候时空复杂度都是没错的，就是因为没有滚掉一维被卡常数了，当然我觉得这样的情况发生的概率特别特别小，没有人会去卡这点常数罢。
于 2023.11.26 14:00
也是动态规划的引入
滑雪：雪啊，食雪啊
有些时候dp好写，有些时候记忆化好写，但这两个东西的本质是一样的，这题适合记忆化，考虑将高度从低到高排序，直接记忆化搜索即可。
$ $
最大食物链计数：这真的算dp吗？
$ $
考虑直接 dp，这里直接给柿子 \(ans=\max(sum+x,x,ans)\) ，ans 初值为负无穷。
$ $
整数划分没找到。那么动态规划的引入就写完力。
于 2023.11.28 22:20
昨天出分了，本来以为自己垫底稳了，没想到还有【数据删除】帮我垫底，快乐多了
sakana 还有 WQ最大fAKer 在和 THOTH 商量 WC 的事情，我 CSP 考太烂了，只能自娱自乐了。
写了会 whk 作业，研究了一下 tuple，搞完已经没多少时间写 dp 了。
导弹拦截：还没写，自己只能想出来 \(n^2\) 的第一问和 \(n\log_2n\) 的第二问，看了题解，感觉第一问的优化有点神奇，我觉得这算个上位黄了。
于 2023.12.2 15:20
今天把片剪完了，累死我了，想要做出好东西来得要多学点。
有一说一，我妈不知道是什么原因开始对我 OI 像对我 whk 一样了，虽然我不太喜欢这样，我还是喜欢自己搞，但至少比之前有大进步了，估摸着还是班主任说的话有用，得亏班主任支持啊，对于初中班主任我就只能 流汗黄豆——差不多得了 的态度。
接着导弹拦截：
首先第一问 \(n^2\) 的方法是好想的 \(dp_i=\max\left \{1,max_{1\le j<i,h_i\le h_j}dp_j\right \}\) ， \(ans=\max_{1\le i\le n}{dp_i}\) 我觉得显然，第二问 \(n\log_2 n\) 的也是好想的，我们令可重集合 \(S\) 为当前所有已部署的拦截系统所能拦截的最高高度的可重集合，当遭受一个导弹攻击时，我们选择高于当前导弹的拦截最高高度最低的系统对他拦截，如果没有就新开一个系统，并加入 \(S\) ，显然，答案是 \(S\) 的大小，使用二分就可以在 \(n\log_2 n\) 时间内解决。
关键在于第一问的 \(n\log_2 n\) ，其实只要知道了结论就很简单，先给出结论：
记 \(f_i\) 表示「对于所有长度为 \(i\) 的单调不升子序列，它的最后一项的大小」的最大值。特别地，若不存在则 \(f_i=0\) ，而且随 \(i\) 增大，\(f_i\) 单调不增。
证明有点绕，但是光看结论还是比较显然，感性理解一下就是了，证明链接。
然后就可以对 \(f\) 进行二分，找出满足最大的 \(1\le j\le maxlen\) 使 \(f_j\ge h_i\) 即可，接着对 \(maxlen\) 进行更新，答案即为 \(maxlen\)。
于 2023.12.5 19:00
今天听新闻听到关于明年的新闻了，想了想才发现时间过的好快啊，转眼就快要到明年了，只剩 26 天了。
今天继续写洛谷题单。
打鼹鼠：有一说一，我还一开始真不知道怎么下手，思考无果就去看了题解，发现自己是个若至，一看方程我就懂了，脑子还是没转过那个弯来。
我们将每个鼹鼠的出现时间排序，虽然说题目已经给我们排好序了，\(dp_i\) 表示到第 \(i\) 只鼹鼠最多能打几只鼹鼠，转移方程为 \(dp_i=\max_{1\le j<i}(dp_i,dp_j+1)\) ，条件是 \(time_j+|x_i-x_j|+|y_i-y_j|\le time_i\) 时间复杂度为 \(m^2\) ，因为我们在当前鼹鼠的最大值肯定是从之前的鼹鼠转移过来的，所以如此设计转移方程。
$ $
琪露诺:这个我会，但是 \(n^2\) ，范围 2e5 ，虽然但是，\(O2\) 艹过去了。数据有点氵。
直接给方程了，我发现这些题如果不写优化都一个套路。
$ $
于 2023.12.7 22:00
本来可以写两题的，写个英语作业写了好久，都是英语害得的
今天继续
大师：这我只会 \(n^2v\) ，还是菜了。看了题解，发现确实是自己菜。
自己的解释就放代码里：
for (int i = 1; i <= n;i++){
for (int j = 1; j < i;j++){
dp[i][h[i] - h[j] + v] += dp[j][h[i] - h[j] + v] + 1;
//表示由第 j 项与它们二者之间的高度差转移而来
dp[i][h[i] - h[j] + v] %= MOD;
ans += dp[j][h[i] - h[j] + v]+1;
//因为 dp 数组中存的是以 i 结尾的等差数列长度 - 1
//而当前的方案数应为等差数列的长度，所以 + 1
ans %= MOD;
}
}
题解写的比我好多了，再放一份题解的：
"
以 \(i\) 结尾且上一个数是 \(j\) 的公差为 \(k\) 的等差数列数量是以 \(j\) 结尾公差为 \(k\) 的等差数列数加一
转移的过程中直接计数，顺便把数字数为一的区间加上
注意第二维数组开二倍将负数右移即可
这样只需要 \(n^2\) 的转移就可以了
"
于 2023.12.9
md，写了一上午WC2018结果看不懂样例，导致暴力寄掉，最ex的是我手%的和我程序算的一样，换了种理解方式再算一遍发现和样例不一样，难受，艹。
火大，继续。
快速求和：
luogu月赛，启动！
小丑了，对着 1A 大眼瞪小眼瞪了一下午，最后烦躁的要死没写一道题，乐
于 2023.12.12 22:00
今天出了省队名额，JX 6个名额
md，这下多切一题都没队进了。
THOTH 找了 Sakana 和 WQ最大fAKer 谈话，叫他们不要太功利，我不一样，菜到没办法功利。
写了一会网络流，没有给初始流量赋初值卡了20分钟，md。
快速求和：昨天就写完了，忘记写了，有一说一，我觉得这数据是有点氵的，题解那种限制数字位数到11的做法实在是不可取，于是我进行了一下修改，而且打算出一个 HACK ，当然也有咕咕咕的可能性。（如果看到我还没有去hack就踢下我） HACK 完成于 2023.12.14
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0);
cout.tie(0);
string s;
ll n, len;
cin >> s >> n;
len = s.size();
for (int i = 0; i < s.size(); i++)
{
a[i + 1] = s[i] - '0';
}
for (ll i = 1; i <= len; i++)
{
num[i][i] = a[i];
for (ll j = i + 1; j - i <= len - 1 && j <= len; j++)
{
if ((num[i][j - 1] * 10 + a[j] <= n))
num[i][j] = num[i][j - 1] * 10 + a[j];
else
num[i][j] = INT_MAX;
}
}
memset(dp, 0x7f, sizeof dp);
dp[0][0] = 0;
for (ll i = 1; i <= len; i++)
for (ll k = 1; k <= len - 1; k++)
if (i >= k)
for (ll j = num[i - k + 1][i]; j <= n; j++)
dp[i][j] = min(dp[i][j], dp[i - k][j - num[i - k + 1][i]] + 1);
if (dp[len][n] > len)
cout << -1;
else
cout << dp[len][n] - 1;
return 0;
}
石子合并（弱化版）：
漏了合并后贡献卡了一会，10 分钟氵了。
最长上升子序列（LIS）:
2 分钟氵了。
于 2023.12.14
【数据删除】 去【数据删除】了，周六才能回。不知道【数据删除】的人怎么看待【数据删除】的人。
今天大概就可以结束这个题单了，明两天换题单写
子串：写完了，没时间来写记录了，过几天来补。
于 2023.12.16
写区间dp咯。
回文字串：这是区间dp吗？
考虑求出最长回文子串，然后用原串长度减去最长回文子串长度就是最后的答案，求最长回文子串可以将原串翻转，然后用翻转串和原串做最长公共子序列就可以求出了。
考虑感性证明，我们求出了最长回文子串，那么我们有两种情况，一是该子串长度为奇，那么就以这个字符为回文串的中点，只要是回文子串里的字符都会对称分布，如果回文子串中两个字符在原串是隔开的，那么就可以把隔开他们的字符加到回文子串对应的另外两个字符间，这样我们就可以保证他们在原串是回文的，而且被加过去的字符也刚好回文了；如果长度是偶，那就在直接按照定过中点后的方法做。
Zuma:脑子转过弯来就是板题了。
考虑给基础的转移加上一个语句，我们知道如果 \(a_l=a_r\)，那么会有：
因为若 \(a_l=a_r\)，那就可以直接从夹在 \(l\) 和 \(r\) 的这个区间转移从而达到不需要额外贡献直接消除 \(l\) 和 \(r\)，但是还是要进行一层转移，因为通过下一层转移而来的值是完全有可能会更小的。
合唱队：居然是罕见的 \(n^2\) 区间 dp 口牙
设 \(dp_{i,j,k},k\in [1,0]\) 表示，在区间 \([i,j]\) 上最后一次操作是从前 (0) 插入，还是从后（1）插入，那么显然我们就有 4 种转移可能，分别是
-
从前插入
- 前一次操作是从前插入
- 前一次操作是从后插入
-
从后插入
- 前一次操作是从前插入
- 前一次操作是从后插入
对应到转移方程就是：
if(a[i]<a[i+1])
dp[i][r][0] += dp[i + 1][r][0];
if(a[i]<a[r])
dp[i][r][0] += dp[i + 1][r][1];
if (a[r] > a[i])
dp[i][r][1] += dp[i][r - 1][0];
if(a[r]>a[r-1])
dp[i][r][1] += dp[i][r - 1][1];
初始状态为一个数从前插入的方案为 1，从后也行，但不能二者皆有。
最后答案即为 \(dp_{1,n,0} + dp_{1,n,1}\)。
环状最大两段子段和：还没做，这题绿低了罢，怎么着也得是蓝罢。
今天不写了，滚去写建模题了。
于 2023.12.19
双子序列最大和：下一题的前置，5分钟氵了。没必要放方程。
环状最大两段子段和：是我菜了，sakana 教过就会乐，(TヘTo)
类似于反悔贪心的做法
基础和上一问一样，正着扫一遍，反着扫一遍，此时求出最大双子段和，然后对整个序列取反，再求一遍最大双子段和，用原序列的总和减去这次所求的，再和第一次求的最大双子段和取个 max 就求出答案来了。
取反后选择的两段
用 sum 减去后等同于
相当于在环形上求最大双子段和。
今天开始推树上与图上 dp 。
二叉苹果树：裸的树形背包。脑袋卡壳了花了点时间。放一下转移方程。
设 \(dp_{x,k}\) 表示在节点 \(x\) 保留 \(k\) 个树枝
则
注意倒着扫就是了。
跑路：这题其实没有说有什么 dp 罢，主要还是倍增，真要说 dp 难道是 floyd ？
一开始本来直接过了，结果因为初值赋太大导致 floyd 跑得时候越界了，这里要记住 memset(f,0x7f,sizeof f) 时，\(2f\) 会越界，memset(f,0x3f,sizeof f) 不会。
于 2023.12.21
今天只看日期是回文日awa。
明天考试，后天考试，笑死我了。
今天继续树图dp
绿豆蛙的归宿：拓扑板题，期望知识没过关，卡了一会，实际上很氵，直接 PASS。
采蘑菇：个人认为难度不高，就是这个抽象缩点重赋点权重建图图上拓扑序转移dp，看起来很难实际上不会，就是恶心。还没写完。先写思路。
显然先缩点，然后将每个强连通分量里的所有边权压成点权，然后重新建图，按着拓扑序直接转移就是了，感觉不如环状最大两段子段和。
于 2023.12.25
笑死，月考爆炸了，物理写太慢导致没写完，前面还把正确的改成错误的；数学也没写完，因为三角函数算错值导致图像画好久耽误了时间，前面有一个没注意cos的取值导致从选择全对变成扣5分；语文意外作文上了40,有点惊讶，但这次还是差 3 分及格；英语也就那样了；生物差1分及格，结果这次不赋分，小丑了；化学也就那样了，要不是那个方程没配出来，不然就上70了，居然比 WQ最大fAKer 高一分；总分成信息组最丢脸的了（除去【数据删除】）。生物【数据删除】那边改出来59，我们这边改出来64。XD
听 THOTH 说又要停课了，不知道怎么搞，whk这边说好看罢，在班上排挺后的，说不好看罢，在年级里又还算比较前的。
有点难办啊。
于 2023.12.26
一年又要过去力，不知不觉又到了一年的末尾呢，想我开始拥有使用竞赛机房的权利还是在今年年初，那个时候才真正成为了一个正式竞赛生吗？但也已经过了一年了，时间好快啊，明年我16岁生日一过就是省选了，不知道自己能不能给自己一个最好的生日礼物呢，大抵是有点困难的，毕竟真的打不过那些怪物啊，希望能让17岁时的我把16和17的礼物都拿到手。
续采蘑菇：拓扑序转移有点问题，起点可能不是 0 入度点，而且不太好搞掉其他 0 入度点的影响，所以改写最长路。
md，m 写成 n 调了1个小时。
火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了。
于 2023.12.28
（2）省选正式参赛资格：
NOIP 2023成绩高于150分（含）；
或
NOIP2023女生赛江西省获奖选手。
这下我开心了，直接去不了省选了，直接线上全真 VP 。
火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了
很难受，写不动题了，虽然说还有一年，虽然比我强很多的学长都放下了，但是，但是，但是，唉。
md。年轻人复活甲叠的就是快，老子复活了，明年再战就明年再战，ctmd。