为了补上我dp的短板（其实说真的dp约等于没学过，板都没有的那种），也为了以后复习dp不会再忘记dp怎么写，dp的各种思想是怎么来的，从零开始学习 dp ，并记录在此博客。
当然也会记录日常生活
大概是首发于洛谷博客，可能会同步到博客园，以后搭了个人blog就会同步到个人blog。
有一些题目加上了 <\(\text{trick}\)> 标签方便以后复习技巧找，使用 Ctrl+F 即可
洛谷blog指路
博客园指路
个人blog指路（暂无）
于 2023.11.23 22:00
今日写了 洛谷题单 - 动态规划的引入 思维导图里的题
虽然是基础题，但基础不牢，地动山摇，更何况我是真的有题不会（没错就是基础题不会）
$ $
纸币问题1：没什么好讲的我都写的出 要用一些不同面值的纸币凑出一个金额，每种纸币无数张，问最少用多少张可凑出。
如果要求最少使用张数，我们可以知道最后这个金额肯定是要从前面某个金额的最小使用张数+1而来，那么就可以从1枚举到最后金额，求出每个金额的最小使用张数一个个转移就是。
$ $
数字三角形：这是真的没什么好讲的了。
$ $
纸币问题2：不讲题面了
题目说了顺序不同也算一种方案，那么我们就可以从1转移到最后金额，当前金额方案数等于前面所有可以通过加上某个面值后等于当前金额的金额的方案数的和
$ $
纸币问题3：
现在顺序不同不能算贡献了，考虑外层枚举面额，内层枚举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 //而当前的方案数应为等差数列的长度，所以 + 1ans %= 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];elsenum[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;elsecout << 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分钟氵了。没必要放方程。
环状最大两段子段和：<\(\text{trick}\)>
是我菜了，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
CCF NOI 2024江西省队选拔赛报名通知
（2）省选正式参赛资格：
NOIP 2023成绩高于150分（含）；
或
NOIP2023女生赛江西省获奖选手。
这下我开心了，直接去不了省选了，直接线上全真 VP 。
火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了火大了
很难受，写不动题了，虽然说还有一年，虽然比我强很多的学长都放下了，但是，但是，但是，唉。
md。年轻人复活甲叠的就是快，老子复活了，明年再战就明年再战，ctmd。
于 2023.12.29
我今天的烦躁程度远超我想象，看来还是有点难受，我现在就一个念想，那就是不正式参赛也要到省选赛场上比一比，就只有这个是我最希望的了，虽然能正式参赛就更好就是了。
明两天又是待在学校集训，说实话我真的因为这个事情动力减少了很多，但是没办法，就算是为了高二的省选做准备了。
高情商：
这是眼光长远地为高二省选做准备。
低情商：
就是菜。
接下来的计划就变更了，我可以开始准备更为长远的数学学习了，OI 上也可以开始放长线学习计划了，首先 dp 是不可以断的，因为本来就菜，后面看一下是先去搞各类数据结构还是先去搞图论，如果有余力的话还是要出出题，毕竟这也是提升实力的重要途径，也可以体验当毒瘤的感觉，还有搞点什么黑科技，不能总局限于已有的东西，虽然这个的优先级肯定是最低的了，毕竟我还是很菜，还有就是要搞 dark♂ 模拟，代码实现能力要拉上去。
就这样罢，明天开始进状压 dp 了，后面就是各种 dp 优化。
于 2023.12.30
今日状压 dp
依旧是按着题单走
互不侵犯：
很容易可以想到状压，每个位置选与不选可以让每行组成一个二进制数，一下就想到了。
一开始我设的状态有四维 \(dp_{i,j,k,c}\) 表示第 \(i\) 行第 \(j\) 列已经选了 \(k\) 个并且当前行的选择情况为 \(c\)，然后发现状态重合了，因为 \(c\) 的大小已经可以表示是在第几列了，所以就改成三维 \(dp_{i,j,k}\) 表示第 \(i\) 行，选择情况为 \(j\)，已经选了 \(k\) 个。
然后就可以想到转移方程为
上式中 \(c\) 表示总选择状态，\(num_j\) 表示选择情况为 \(j\) 时有多少个被选了，若 \(num_j=-1\) 则该选择情况不合法。
上式可以执行当且仅当 num[z] == -1 || (z & j) || (z & (j << 1)) || ((z << 1) & j) 该式为假时可以执行。
边界条件为 \(dp_{1,i,num_i}=1\) 其中 \(i\) 为所有满足条件的选择情况。
循环时注意边界即可。
啊啊啊不想写dp乐，我已经很长时间没有接触过 dp 以外的题乐，开始营养不良乐。
于 2024.1.2
新年快乐！（虽然迟到了
啊，已经是 2024 了啊，虽然农历还没到，时间过的好快啊。
不多讲了，继续 dp。
今天还是在状压 dp。
关灯问题II：
原题的操作有点绕弯子，这里直接翻译成人话。
有 \(m\) 个按键，\(n\) 个灯。每个按键按下后会对这 \(n\) 个灯进行调整。按下 \(i\) 按键对于第 \(j\) 盏灯，是下面 3 中效果之一：若 \(a_{i,j}=1\) 则将该灯调整为关；若 \(a_{i,j}=-1\) 则将该灯调整为开；若 \(a_{i,j}=0\) 则不调整。初始所有灯都是开的，求最少按多少次按键可以关掉所有灯，若无论怎样都无法关闭所有灯，则输出 \(-1\) 。
事实证明乱搞可以过。
首先考虑压缩状态，灯的状态就不需要说了，正常压缩，接下来考虑按钮带来的影响的状态
我们考虑压两个数字，第一个数字代表所有的 \(a_{i,j}=1\)，第二个数字代表所有的 \(a_{i,j}=-1\)，我们令 \(val_1=2^n-1,val_2=0\)，对于每一位若 \(a_{i,j}=1\) 则 \(val_1\) 的该位变为 \(0\)，若 \(a_{i,j}=-1\) 则 \(val_2\) 的该位变成 \(1\) 这样转移的时候就可以从状态 \(i\) 转移到状态 \(i\&val_1|val_2\) 这样就做到了 \(O(1)\) 的转移，然后考虑所有按键都按 \(T\) 遍能不能转移到 \(0\) ，时间复杂度 \(O(T2^nm)\) 我取的 \(T=100\) 因为考虑到他有 \(100\) 个按键所以跑 \(100\) 应该就可以得出最终解，虽然我觉得这样可能不太正确，但或许没办法卡掉（至少我不会。
while (T--)
{for (int i = anx; i >= 0; i--){if (dp[i] != inf)for (int j = 1; j <= m; j++){to = i & cg[j][0] | cg[j][1];dp[to] = min(dp[to], dp[i] + 1);}}
}
事实证明因为数据过氵 \(T=2\) 就可以直接过所有数据，\(T=1\) 过不了 hack。
这里我想到了实际上的证明方法，也就是说不会被卡掉，而且可以优化复杂度。令 \(T=m\)，那么复杂度就变成了 \(O(2^nm^2)\)，是十分优秀的复杂度，他的范围再大点都没关系。
考虑将问题转化为图上问题，从每个状态开始，看从这个状态按下每个按键可以转移到哪个状态，然后连一条有向边，最后跑一遍最短路就行乐，我这样子写就类似于跑 floyd，是吗？是的罢后面看一下找个时间 hack 了。
为什么我从开始写状压 dp 后写的就越来越长了啊。
A Simple Task：不会写，不知道这种东西怎么转移的，看了题解懂了，想起了 CSPRO 的闪耀巡航。
写完了，过几天补一下笔记。
破 \(500\) 行庆祝！
于 2024.1.4
今天你校英语节，被二五仔背刺了。
接 A Simple Task：
状态压缩方式就不多说，选与不选的压。
类似于 floyd 的，令当前状态为 \(t\) 则起点为 \(lowbit(t)\)，一步步中转最后看能否走到起点即 \(lowbit(t)\) 若能，则加入答案中，若目前不是起点，则转移贡献到当前点。
宝藏：
md帮人调费用流调红温了。
后面补，还不会写。
于 2024.1.5
今天 WQ 最大 fAKer 和 sAKana 去外培了，我太菜了，打不了省选，伤心。
于 2024.1.6
宝藏：
写完了，还是看了题解，这东西的压缩方式我还以为会很复杂，因为觉得存在树异构的情况，只压已选点无法知道树的结构，也就无法求出树的总代价。所以我一开始是往用一种方式来表达一个树的结构然后压缩，并在这个树上进行换根 dp 以求出该结构的最小代价进而求出全部树的最小总代价，但是复杂度实在有点高，没去写，而且没想到怎么优化。
看了题解就知道了实际上完全不用考虑异构的问题。
正常压缩。
设 \(dp_{s,h}\) 为点集为 \(s\) 时树最大高度为 \(h\)，令 \(\sout{G_s}\) 为 \(\sout s\) 可扩展出的所有集合的并，\(s_0\) 为 \(s\) 的非空真子集。
初始状态为 \(dp_{1<<i,0}=0,0\le i< n\)，其余均为极大值。
转移方程为：
其中 \(cost\) 计算方式如下：
令 \(\large g=\complement_s s_0\) 即使用位运算的 \(g=s \oplus s_o\)，\(w_i=\min dis_{i,j}\)，\(sum=\sum w_i\) 其中 \(i\in g,j\in s_0\)
则 \(cost=sum\cdot h\)
注意到我们的计算方式是对于点的集合而言的，也就是计算方式本身就没考虑树异构的情况。
现在解释为什么不用考虑树异构的问题。（当然是有一点感性理解在里面的
首先我们规定了高度是多少，那么相对而言树的结构是有一定的确定性的，如果对于 \(s_0\)，其加入的边不是全部与该子集的某一结构的最大深度点相连，那么从这个子集转移一定会更劣，最终想要的结构一定可以从另一个子集转移而来，并且所连边接在最大深度点上。
至于时间复杂度，由于我比较菜，不会证明，只知道是 \(O(3^nn^2)\)。
啊啊，今天的 dp 就到这里罢。有点想念数据结构和网络流了。
于 2024.1.7
下午三点就被抓来学校了，难受QAQ。
于 2024.1.9
BJWC2018 那题过段时间写，因为不会杨表之类的，也不太像是能用状压过的去的题，后面实力更强一点再去写，顺便可以写写题解。
一双木棋：<\(\text{trick}\)>
这道题压状态的方式好巧妙啊，这就是轮廓线 dp 吗？学到了学到了。
也学了一下 min-max 搜索，还不错，这是我第一个学会了的博弈相关算法。
先讲一下状态压缩，我们知道整个棋盘有足足 100 个格子，每个都压进去的话大小是可想而知的，不仅空间过不去，时间更不可能过去。然后注意到我们所下的棋所构成的图形一定是个连通块，每行棋子是连续的，且满足 \(num_i\le num_{i-1}\)，\(num_i\) 表示第 \(i\) 行的已下棋子数，也就是众多题解所说的“锯齿形”。
本来仔细写了状态为什么不会重叠的问题，但因为没有保存，然后使用 desmos 不当导致浏览器崩溃，所以没了，这里就简略写一下。当 \(\sum_i^nsum_i\) 为奇时，一定是先手下到的状态；为偶时一定时后手下到的状态，所以状态不会重叠。
最后写一下如何求解，实际上本题难点就在于如何进行状态压缩，懂了如何进行状态压缩就是裸的 min-max 搜索，根据计算，有效状态不多，可以使用 map 存下每个状态的值，然后视先手为最大化价值，后手为最小化价值，输出根节点即 0 状态的答案即可。
花园：
是我菜了，不会融汇贯通，先不谈矩阵加速，只谈暴力，这个不只是压缩状态然后直接进行转移，还要按像以前写的 dp 一样一步一步转移到 n。还没写，瞥了一眼题解，看后面自己想能不能想出来。
于 2024.1.16
emmmm 过了挺久的，虽然不是没写题，但没写 dp，在自己出题，有点耗时，毕竟是第一次出题，虽然出的是氵模拟。
在加上前几天状态不是很好，晚上还有点失眠，就没写多少，尽在那里氵了，THOTH 说我在迷茫，我到底是不是在迷茫呢？我说不清。
今天继续写 dp，看能不能把思维导图里的题写完。
还是花园：
呃呃还是菜的，不会写，还是看了题解。
写这题顺带复习了一下矩阵。
考虑将第 \(i\) 位的前面 \(m\) 位进行压缩。
令 \(dp_{i,j}\) 为第 \(i\) 位的前面 \(m\) 位 的状态为 \(j\)，\(\text{bitcount(i)}\) 表示 \(i\) 有多少位是 1。
转移方程如下：
\(\large dp_{i,j}=dp_{i-1,j>>1}\)
条件为：
\(\text{bitcount(j>>1)}\le k\)
啊啊，不想写了，直接进构造矩阵。
对于任意状态 \(i\) 可以转移到状态 \(con\) 的，令 \(A_{con,j}=1\)，其余为 0。
正常矩阵快速幂。
\(ans=\sum_{i=1}^nA_{i,i}\)。
于 2024.1.18
笑死，我出的氵比%你【数据删除】写了两个多小时，他宁愿承认自己菜也不愿意承认我的题好，虽然我自己都觉得这是道大氵题。
今天把状压 dp 思维导图上的题都搞好了，再写一些后面进 dp 题单六了。
硬币购物：
一道小清新题。虽然我还是不会
要是直接写多重背包会挂掉，我们可以先跑一遍完全背包然后考虑对背包方案数进行容斥。
首先基础的答案就是 \(f_s\)，在此基础上使用次数超过了的情况就减掉，很显然是需要容斥，于是我们按照下面来写。（最主要的是我比较懒，不想写解释了）
for (int con = 1; con <= 15; con++)
{co = s;k = 0;for (int sc = con, j = 1; sc;sc>>=1,j++)if(sc&1){k ^= 1;co -= (d[j] + 1) * c[j];}if(co>=0){if(k&1)ans -= f[co];elseans += f[co];}
}
于 2024.1.18
最近九省联考，THOTH 就让我去看看数学的最后一题，我还说估计我还没学，写不出来，结果一看是初等数论，然后用一大堆难看的符号和过于简单易懂的语言掩盖住这其实就是一个大氵题的本质，就是接触过初等数论的人都觉得这题氵，而且题面很难看，没接触过的就觉得很难，只会代值算算第一小问，而且题面很难看。有一说一，他搞一个形式化题面我很快就可以写完，实际上还是读题花了时间。
易掩丁真，鉴定为：
大氵货。
今天还是在搞状压，我倒是总结出一个方法来了。
邦邦的大合唱站队：
支持 \(\mathit {BanG Dream! It's MyGo!!!!!}\) 喵！
支持 \(\mathit {BanG Dream! It's MyGo!!!!!}\) 谢谢喵！
一步一步来罢。
人数很多，但是乐队只有 20 个，而且同一乐队的 idol 要站在一起，所以可以考虑乐队的排列来代替人员的排列。
首先是最容易的 \(O(m!n)\)：
很容易想到枚举 m 个乐队的全排列，然后在从 1 到 n 一个一个检查当前位置的 idol 是不是之前也站这里，然后就可以求出当前排列的答案，进而求出最终的答案。
这样子裸做可以得到 40pts，加上卡时可以得到 70pts。
考虑优化，比较容易想到的就是用前缀和来优化一个一个检查的过程，毕竟乐队人数是知道的，这个乐队所占的区间也就知道了，优化成 \(O(m!)\)。
裸做 70pts，加卡时 80pts。可见这题的能乱搞的可能性还是比较高的，不过这里不讨论。
然后就是状压 dp 的 \(O(2^mm)\)，实际上状压的做法与前面的做法有直接关联的就是前缀和优化了，其他的有题解说是剪枝，要这样说也没错，但我不太赞同就是了。
正常压缩，令 \(S\) 表示已经排好的乐队集合，\(num_i\) 表示乐队 \(i\) 的人数，\(sum_{i,j}\) 表示前 \(i\) 个人中有几个是乐队 \(j\) 的，\(len\) 表示集合 \(S\) 中所有乐队的总人数，\(f_S\) 表示当前状态为 \(S\) 时的最小花费是多少，转移方程如下：
实际上这个方程的意思就是令集合 \(S\) 中最后一个加入的乐队是 \(i\)，从而就不用处理顺序的问题，后面的价值就比较显然了，最后一个加入的乐队的贡献会等于该乐队人数减去该乐队所在区间原有人数，因为我们知道集合 \(S\) 中包括了那些乐队，所以可以知道最后一个加入的乐队的所在区间。
这里总结一下这一类题的做法：<\(\text{trick}\)>
像这种部分数据大，部分数据小，明显有状压倾向的题，但看上去可能要考虑同构、异构、顺序等等等等，而导致状压似乎不可行的题，可以考虑不去管那些可能会影响答案的因素，就专注于集合到集合之间的转移，比较典型的就是本题和宝藏那题，然后偏的比较远的但我还是认为属于这一类的还有花园算是另一种典型。
砝码称重：
还算是比较氵的，毕竟我会做而且是一眼，氵题不写解析。
Meeting Time S：
本来是在随机跳题的，既然跳到了 dp 就写一下。
有一说一，我之前遇到的所谓拓扑序 dp 实际上没有感受到很多的 dp 思想，大多都是一个拓扑排序套上一定的计算的式子就结束了（虽然这题也是），而这题至少有一点点是要思考的。
一开始我设的方程是 \(dp_{i,j}\) 表示从点 \(1\) 走到点 \(i\) 且由点 \(j\) 转移而来的时间，忽略了会有不同的路径导致时间不一样，而且重点有点放错了地方。
正确的状态设计应该为 \(dp_{i,t}\) 表示存在路径从点 \(1\) 走到点 \(i\) 使得时间为 \(t\)。
看到这里就都会写了，就是个背包套拓扑。方程显然，不写了。
于 2024.1.22
今天好冷，还下雪了，人生中第一次看见下雪，还是在 JX，还好机房没开门开窗，不然机房就会冷死人。
南国之雪啊。
今天开始“动态规划的设计与优化”题单了。
逆序对数列：
正常解法还好但是据说 loj 上有一个超大范围的加强版，加强版的三种解法都好抽象，改天看看。
于 2024.1.23
今天是很重要的日子，不仅是开始写这个 dp-record 的恰好两个月，也是期末考开考的日子。
今天考了生物，和上次一样，写的和窜了一样顺，就是不知道考的咋样，虽然出来的时候对答案看上去好像还不错，但是还是不清楚。
话说【数据删除】的改卷速度这么快的吗？今天考了哪门，哪门就要在晚上十点以前改完，这么恐怖。
于 2024.1.24
今天考语文英语物理。
下午考完的，语文依旧 40 分钟 900 字，英语读后续写依旧 15 分钟写完，物理还是没写完，又是因为题目看错导致重算一遍，难受。
明天就考完了，后天就出成寄。
于 2024.1.25
今天考化学数学。
考完力！！！！！
化学卷子上强度了，难蚌只有 60～70 乐，数学卷子有点氵，虽然我只有 130 左右，现在谈到数学卷子就气，填空题向量的模没开根，范围多乘了个 \(e\)，然后画错图像导致多选错一个，看错柿子导致单选第七题写了好久，浪费时间，最后还没写完，传统美德。
Power收集：
有点氵，感觉不值得蓝，一眼秒了。
考虑状态设计
设 \(dp_{i,j}\) 表示第 \(i\) 行，第 \(j\) 列的最大 power 值是多少。
转移显然 \(dp_{i,j}=\max dp_{i-1,k}+val_{i,j}\) 其中 \(\max (j-t)\le k \le \min (j+t,m)\)
显然单调队列优化，令 \(x\) 为单调队列队头元素，则转移方程化为：
\(dp_{i,j}=x+val_{i,j}\)
完事
于 2024.1.27
The Bakery：
应该是经典线段树优化 dp 了罢。
状态设计不会难，令 \(dp_{i,k}\) 表示到第 \(i\) 位，已经分了 \(k\) 段，\(val_{i,j}\) 表示从 \(i\) 到 \(j\) 有多少个不同的数。
最最最朴素的是 \(O(n^3k)\)
\(dp_{i,k}=\max_{1\le j< i} dp_{j,k-1}+val_{j+1,i}\)
外层 \(i,k\)，内层 \(j\) 和每一次求 \(val\) 都扫一遍 \(O(n)\)
乘起来 \(O(n^3k)\)
考虑将扫一遍内层 \(j\) 的过程与求 \(val\) 的过程合并，倒着扫，就可以依次求出 \(val\)，不需要再扫一遍。
优化为 \(O(n^2k)\)。
for (int i = 1; i <= n; i++)
{for (int j = 2; j <= k; j++){vis.reset();vis[val[i]] = 1;cnt = 1;for (int z = i - 1; z > 0; z--){dp[i][j] = max(dp[i][j], dp[z][j - 1] + cnt);cnt += (!vis[val[z]]);vis[val[z]] = 1;}}
}
显然还是过不去。
考虑再对其进行优化。
我们再换个角度思考，将原本在更里层的 \(k\) 和在更外层的 \(i\) 交换，即先求完 \([1,n]\) 的分 \(k\) 段的值，再接着求 \([1,n]\) 分 \(k+1\) 段的值，而不是先求完 \(i\) 的所有分 \([1,k_{max}]\) 段值再转移到 \(i+1\)。
如果这样做我们就会发现所有的分 \(k-1\) 段的值都是已知的，我们只要考虑怎么求出 \(val\) 对其的影响。
可以发现 \(dp_{j,k-1}+val_{j+1,i}\) 本质上就是将已经求好的在区间 \([1,i-1]\) 上的 \(dp\) 值，再拼接上一段，最后找到最大的从而转移到 \(dp_{i,k}\)。
首先求最大可以很容易想到线段树；然后所有分 \(k-1\) 段的值都是已知的，所以我们对每个 \(k\) 都基于 \(dp_{i,k-1}\) 建一颗线段树；因为是再拼接上一段 \([j+1,i]\) 所以可以想到扫的时候可以把在 \([j+1,i]\) 上出现的不同数值的贡献直接加到 \(dp_{j-1,k-1}\) 上，这样就符合转移的方程，所以线段树每个叶节点的值是 \(dp_{i-1,k-1}\)，但是如何确定数值的贡献呢。考虑令 \(fr_i\) 表示在 \(i\) 上的数值上一次出现的地方加一，我们可以在扫的时候直接将在 \([fr_i,i]\) 上的 \(dp\) 值加一，这样就不会因为是同一个数字重复加入，也不会因为后面的 \(dp_{i,k}\) 因为转移的 \(j\) 大于当前的 \(i\) 而错误记入。
时间复杂度 \(O(nk\log_2n)\)
天天爱打卡：
来了，断送我省选的题目，现在的我已经会了当初不会的 52pts 做法，后面再继续搞，你是我的重点对象
于 2024.1.29
天天爱打卡：
md，52pts 做法挂成 44 分做法了，我这个好像是 \(O(m^2)\) 的。
于 2024.1.30
今天第一次打 USACO，ak 铜组，可惜没时间写银组了。
天天爱打卡：
OHHHHHHHHHHHHHHHHHHHHH！
写出来力！！！！！
第一次自己写出线段树优化 dp，而且实际上写法基本和所有题解都不一样。
甚至我认为的大常数代码都不需要卡常。
虽然调的很难受，但总算是解决了这个重点对象。
有点晚了，过几天再补。
于 2024.1.31
今天打了云斗，还是自己菜了，只会一两题，不过可喜的是我能把暴力 dp 写出来乐，大抵是有钱拿的。
补一下天天爱打卡。
考虑最基础的 \(O(nmk)\) 的做法。
设 \(dp_i\) 表示第 \(i\) 天不跑所得的最大能量是多少。
转移方程为：
其中 \(sum_{j,i}\) 表示从第 \(j\) 天到第 \(i\) 天有效的挑战所提供的贡献和。
代码如下：
for (ll i = 1; i <= n+1; i++)
{sum = 0;for (ll j = i - 1; j >= max(i - k - 1, 0ll); j--){for(auto px:val[j+1])if(i-1>=px.first)sum += px.second;dp[i] = max(dp[i], dp[j] - d * (i - j - 1) + sum);}ans = max(ans, dp[i]);
}
其中 \(val_i\) 存储的是在第 \(i\) 天开始的挑战的结束日期以及所能提供的能量值。
考虑优化。
我们发现有用的天数只有各个挑战的端点值，所以可以将各个挑战的左右端点离散化出来。
考虑离散化后的数组 \(ch_i\)，\(ch_i\) 中对于挑战的左端点 first 存储他的开始日期减一，second 存储他的终止日期，third 存储完成这个挑战可获得的能量值。而右端点，first 存储他的结束日期加一，second 不存储，但为了方便，我们存为极大值，third 也不存储，但为了方便，存为 \(0\)。接着对 \(ch\) 排序，那么我们就得到了离散化的数组。
其他地方小改一下就可以了，时间复杂度 \(O(m^2)\)，但是根据数据强度，上界会比较松，可以得到 44pts。
代码：
for (int i = 0; i < ch.size(); i++)
{x = ch[i].first;sum = 0;for (int j = i - 1; j >= 0 && x - ch[j].first - 1 <= k; j--){x1 = ch[j].first;if (x == x1)continue;y = ch[j].second.first;w = ch[j].second.second;if (x > y)sum += w;dp[i] = max(dp[i], dp[j] + sum - (x - x1 - 1) * d);}if (i)dp[i] = max(dp[i], dp[i - 1]);ans = max(ans, dp[i]);
}
继续考虑优化，我们发现 (x - x1 - 1) * d 可以转化为随着 \(x\) 不断增加，在区间 \([1,x_1]\) 上不断减去 \((x-x_1)*d\) 其中 \(x_1\) 表示上一个 \(x\)。
面对这种区间问题，很显然可以用线段树优化。
这样我们就解决了不同天数导致要减去的能量不同的问题。
再根据我们存储挑战的方式，我们可以知道只有当前天数大于挑战结束日期，且转移天数小于挑战开始天数才能得到挑战的能量。但是我们用线段树维护 \(dp\) 值，加入贡献早了或晚了都会影响 dp 的转移。于是我们考虑将挑战加入优先队列当中，以结束天数为关键字按小根堆入队。当我们到了第 \(i\) 个离散化端点，对优先队列进行处理，如果堆顶的值小于当前离散化端点的天数，就把这个挑战的贡献加入到线段树的 \([1,begin-1]\) 也就是 \(1\) 到该挑战的开始天数减一，因为我们要对线段树进行访问的区间是 \([x-k-1,x]\)（未离散化时），所以即使加到了前面也不会影响求值，毕竟访问不到。
还有一个问题就是就是怎么确定离散化后的区间，这个好想，直接二分左边界，然后我们知道端点是会重复的，所以还要二分右边界，因为没二分右边界卡了好久。
代码。
这下终于搞完了，这道断送省选的题切掉力！
然后刚打完云斗比赛，30￥到手了，最后几分钟老吓人了，真的会有人在最后几分钟狂爬排名啊。
于 2024.2.2
任务安排：
一道斜率优化板题。
考虑暴力 dp（伪）。
已知 \(s\) 只会对后面的任务产生影响，我们就把 \(s\) 的贡献单独拉出来，为 \(s\times \sum_i^n c_i\)。
令 \(dp_i\) 表示完成到第 \(i\) 个任务，\(sumt\) 和 \(sumc\) 分别为时间和价值的前缀和。
然后就可以知道转移方程：
时间复杂度 \(O(n^2)\)。
后面懒得写了。
序列分割：
还是斜率优化板题，甚至比上面的还要板，不写。
找到了一个新的 OJ，加拿大的 DMOJ （大妈OJ），打了一下他的比赛，只能说没有油猴插件太难过日子了。
于 2024.2.2
小年了。
New Year and Original Order：<\(\text{trick}\)>
超级抽象数位 dp，没接触过类似的东西恐怕这辈子都想不出来，后面写。
于 2024.2.4
可能是因为快假期了，虽然有在做，但是懒得写了。
今天打了比赛，洛谷的那场有点火大，ARC 那场我只会 A，属实是菜了，一点不会写啊啊啊啊啊啊啊啊，难受。
PTA-Little Bird：
单调队列优化半板子题。挺氵，不写。
瑰丽华尔兹：
单调队列优化，懒，看着补。
于 2024.2.5
股票交易：
单调队列优化题，有一说一这题的状态也就那样，但是转移方程有点不好想，一开始推了个 \(O(n^2)\) 的转移，和外面两层遍历叠起来时间复杂度到了惊人的 \(O(n^4)\)，想都不用想肯定有锅（虽然正确性没锅），总不可能里一个单调队列优化一个 \(n\)，外一个单调队列优化一个 \(n\) 直接优化到 \(O(n^2)\) 罢。
然后去翻了题解，发现题解比我多一个 \(dp_{i,k}=\max (dp_{i,k},dp_{i-1,k})\) 的转移，然后就发现这样就可以不用再去把前面的所有的 \(j\in[1,i)\) 扫一遍了，因为这个转移已经把前面的都归到 \(dp_{i-1,k}\) 上了。
这里就少一个 \(n\)。
然而我还是没想到怎么用单调队列去优化剩下的那一个 \(n\)。
又去翻了翻题解，发现自己没想出来是因为自己写的有点抽象，一点看不出来。
我自己写的转移是长这样的：
for (int j = 0; j <= min(as[i], k); j++)dp[i][k] = max(dp[i][k], dp[max(i - W - 1, 0)][k - j] - j * ap[i]);
for (int j = 0; j <= min(bs[i], maxP - k); j++)dp[i][k] = max(dp[i][k], dp[max(i - W - 1, 0)][k + j] + j * bp[i]);
把转移对象用一个柿子表达在 dp 里面，把转移产生的贡献直接搞上去。
而题解的转移大抵长这样：
for (int k = 0; k <= maxP; k++)for (int j = max(k - as[i], 0); j <= k; j++)dp[i][k] = max(dp[i][k], dp[max(i - W - 1, 0)][j] - (k-j) * ap[i]);
for (int k = maxP; k >= 0; k--)for (int j = min(k + bs[i], maxP); j >= k; j--)dp[i][k] = max(dp[i][k], dp[max(i - W - 1, 0)][j] + (j - k) * bp[i]);
直接把转移对象放里面，把转移产生贡献用一个表达式写出来后再搞上去。
而题解的转移是可以拆的，可以拆成：
\(dp_{i,k}=\max_{\max(k-as_i,0)\le j\le k} dp_{\max(i-W-1,0),j}-k\times ap_i+j\times ap_i\)
其中 \(k\times ap_i\) 是常数可以直接提出来，所以只要维护 \(dp_{\max(i-W-1,0),j}+j\times ap_i\) 就可以了，而我们知道 \(j\) 的范围长这样 \(\max(k-as_i,0)\le j\le k\)，很可以联想到单调队列，只不过维护的是 \(j\) 而且维护单调队列的表达式是 \(dp_{pos,j}+j\times ap_i\)，而一般写的是直接维护 \(i\)，并且表达式只含有 \(dp_{i,j}\)，所以我会感到有点新奇，可能还是做的少了。
破千行庆祝！✿ヽ( ﾟ▽ﾟ)ノ✿
于 2024.2.17
新年快乐！
其实昨天就被抓来学校乐，只是没有写。
[MtOI2018] 衣服？身外之物！：<\(\text{trick}\)>
观察数据范围，一眼状压。但是第一眼没看出来怎么压，想了想应该不是用二进制而是别的进制，但还是不会写。翻了翻题解发现有两种压的方式，第一种是压 7 位四进制的，另一种是压 4 位七进制的，我想到了第二种，但是不会写转移。然后发现实际上由 \(dp_{i-1,j}\) 推出来 \(dp_{i,j}\) 即使用类似 \(dp_{i,j}=dp_{i-1,j_1}+...\) 的不好想，很难想出怎么正常转移，而写成这种 \(dp_{i+1,j_1}=dp_{i,j}+...\) 形式的就还是很好想的 ，因为知道填哪个衣服就可以由状态 \(j\) 直接对应到一个确定的要转移的状态 \(j_1\)，但同样的情况下被转移的 \(j_1\) 不能对应一个确定的 \(j\)，虽然可以枚举，但终究没前者来的顺畅。
转移方程如下:
其中 \(nt\) 值为 \(nxt(j),+ct_k\times sp_k\)。
\(sp_i=7^i\)，\(nxt\) 函数如下：
ll nxt(ll x){ll ans = x;for (int i = 0; i < n; i++)if(sn[i])ans -= sp[i];return ans;
}
\(sn\) 储存 7 进制下的 \(x\)。
初始状态 \(dp_{0,0}=0\)，其余均为 \(-\infty\)，答案为 \(\max_{i\in S} dp_{m,i}\)，答案为 \(-\infty\) 时输出“gcd loves her clothes!”
于 2024.2.22
鄂鄂。
最近有在做题，但是有些题被要求不能泄漏所以写不上去，然后就是我有在做好多其他的题了，我觉得只记 dp 还是不太够，所以从这天开始就开始记录 dp 题和其他的一些有意思的题目。
Longest Subsequence：<\(\text{trick}\)>
一道比较有意思的题，难度差不多就是蓝，讨论区里说降黄的差不多得了。
考虑 \(\text {lcm} \le m\)，我们就可以把大于 \(m\) 的数全部删掉，这样 \(a_i\) 的数据范围就来到了 \([1,10^6]\)，接着就是本题最精髓的 trick 了。
我们令 \(Lcm_i\) 表示数列里有多少个 \(a=i\)，\(ans_i\) 表示当 \(\text{lcm}=i\) 时最多可以放多少个数进来。显然的，\(ans_i\) 会满足以下式子。
然后我们就可以考虑使用类似筛法的方式从 1 枚举到 m 然后把 \(Lcm_i\) 加到其对应的倍数里去，接着记录最大的 \(ans_i\) 然后就写完了。
至于时间复杂度，实际上等于 \(O(n\log_2n)\)，和埃氏筛的复杂度一样，但是我不会证，好像要用调和级数什么的来证。
于 2024.2.25
距省选还有 5 天。（虽然打体验赛
Height All the Same：<\(\text{trick}\)>
一道神仙题，有趣。
我们发现实际上判断方案可不可行只与高度的奇偶性有关系，而我们可以发现操作 2 不会改变奇偶性，操作 1 可以改变任意两个位置的奇偶性。（因为可以找一条连接两个位置的路径，反复套用操作 1，可以发现路径经过的位置的奇偶性都不会改变。）
然后可以发现只要高度为偶的位置或高度为奇的位置存在偶数个，那么我们就可以通过操作 1 对偶数那方一一配对，从而将所有的偶数方转换为另一方，然后再使用操作二就可以对齐高度了。
那么显然 \(n\times m\) 为奇时是怎样放都成立的，因为总有一方为偶。
此时答案为：
那么 \(n\times m\) 为偶时答案就少一半，虽然我看的是第一篇题解是列出柿子来然后暴力二项式来找到关系，但是我后面还是想到了怎么做，当然，虽然表达不一样，但是柿子本质上是一样的。
这类题一般都只需要关注奇偶性，以后做到类似的可以往这边想。
于 2024.2.27
距省选还有 3 天。（虽然打体验赛
今天你谷的博客变成专栏区了，用起来跟很难评，后台编辑的界面也变得好丑了，尤其是写文本的地方变好小，没有之前的独占中心屏了，之前不用博客园就是因为洛谷博客写文本的地方大，写的舒服，现在变得比博客园还小，不好评价。
在专栏区反馈贴看到了这张图：
然后 cz 和 kkk 切割了，接着发了这张图的评论就全被删了。（被 cz 控评力，悲
餐巾计划问题
之前看到过这题，然后没去做，今天做了一下，是一道建模练习好题。
直接写一下要建哪些边:
以下 \(s\) 表示源点，\(t\) 表示汇点，\(i\) 为第 \(i\) 天，\(n\) 为总天数，\(p\) 为每块毛巾多少钱，\(qt\) 是快洗用时，\(qc\) 为每块毛巾快洗多少钱，\(st\) 是慢洗用时，\(sc\) 是醒目留言是每块毛巾慢洗多少钱。
| \(s\) | \(i\) | \(r_i\) | \(0\) |
|---|---|---|---|
| \(s\) | \(i+n\) | \(r_i\) | \(p\) |
| \(i\) | \(i+1\) | \(\inf\) | \(0\) |
| \(i\) | \(i+qt+n\) | \(\inf\) | \(qc\) |
| \(i\) | \(i+st+n\) | \(\inf\) | \(sc\) |
| \(i+n\) | \(t\) | \(r_i\) | \(0\) |
接下来讲为什么要这样建边。
首先显而易见的是我们拆了点，把 \(i\) 拆成了 \(i\) 与 \(i+n\)，其意义分别为第 \(i\) 天晚上和早上，那么我们建的第一条边的意义就是第 \(i\) 天晚上我们会收到当天产生的脏毛巾，即 \(r_i\)，则最后一条边就是我们每天需要的毛巾量，以这个作限制，就可以满足每天的毛巾需求，第三四五其实都不用说，知道上面讲的什么就很显然，那么第二条就是迫不得已必须买的毛巾数量。
看上去我什么都讲了，实际上我什么都没讲，看上去我什么都没讲，实际上我也什么都讲了。
网络流就是这样，要不你就是看到题解的建模然后恍然大悟，要不就是你干瞪着题解的建模想个半天，实际上还是要积累，积累不同的 trick 的积累多了就会做了，或者指望着哪天写题可以灵光乍现？总之目前我是总结不出什么来，写也只是因为我觉得这个要写。
还是自己比较菜。
酒店之王：
又写了一道。
这题还以为好简单，给我秒了，我还纳闷这怎么紫的，结果一交只有 60 分，下了个数据，再翻了翻题解知道了为什么自己错了。
我一开始直接由源点向每个房间连边，每个房间再向可能的满足条件的菜品连边，最后每个菜品向汇点连边，初始流量定为 \(n\)，以为这样可以满足最大 \(n\) 个人，然后又满足房间菜品都可行的限制。
没错，就是犯了个很低级的错误，一个人不能同时住进两间房，吃两盘菜。
知道错误就很好改了，解决一个人不能住俩房间的问题就 OK 了，直接再加一堆中部点表示每个人，连边就怎么输入怎么连，然后因为加中部点不拆点等于没有限制，会影分身的人还是会影分身，所以还要给中部点拆点，流量显然为 1。
于 2024.3.13
有很长一段时间没写了，主要是在补一些其他的东西，也没心思写。
今明两天开学考 （虽然已经开学半个月多了
上午考了语文，文言文除了翻译都是原题，笑死，寒假作业一点没写，甚至没看，就是在做新题。
作文还是一如寄往。比较不一样的就是这次居然留了 1 个小时来写作文，比之前好很多。
但还是寄。
其他的就不太好说了，下午再写。
下午考了化学生物，化学卷子上出现一个 \(\text{NH}_5\)，我还以为我看错了，没办法只能写一个氨气的化学式上去，考完一搜。
好好好。
生物还是写的跟窜了一样顺，这次甚至还多出 20 多分钟。
明天考英语物理数学。
于 2024.3.14
寄寄寄。
现在已经出了 4 科，化学没及格，要死，生物倒 2，要死。
今天数学把 2013 看成 2023 了，寄，最后一题还没写完，寄。
大寄。
于 2024.3.15
真寄了，班排虽然没动，但是年排退到 70，乐。
昨天写了春测的圣诞树，目前只会 60 分状压，但是不知道为什么写挂了，难受。
于 2024.3.16
今天把圣诞树 60 分部分分写完了，看了一下，dp 过程没错，错在了输出方案，忘记了要倒序输出，然后最高点的高度只更新了点，没更新最高高度，导致寄掉，现在改完乐。
终于开始记录正事乐
[春季测试 2023] 圣诞树：
一道还算小清新的 dp 题。
一步一步来。
60 分暴力：
因为对于 \(60\%\) 的 \(n\le 18\) 数据范围十分之小，这启示我们可以使用状压。
令 \(dp_{con,i}\) 表示状态为 \(con\) 时，最后一个加入的点是 \(i\) 的最小长度，令 \(po_{i}\) 表示第 \(i\) 个点的坐标。
考虑先把最高点找出来，然后将其与最后一位交换，在 dp 和压状态的时候省略最后一位，接着令所有的 \(i<n-1\) \(dp_{1<<i,i}=dis(po_i,po_n)\)，这样就可以保证最高点是第一个被选的，且之后不会重复加入。
最后注意一下记录从哪个点转移而来是要记录当前状态的。
60 分就做完了。
#include <bits/stdc++.h>
#include <bits/extc++.h>
#define ll long long
#define ull unsigned long long
#define m_p make_pair
#define m_t make_tuple
#define inf (0x7f7f7f7f)
#define N 1010
using namespace std;
using namespace __gnu_pbds;
typedef long double ldb;
typedef pair<ldb, ldb> pbb;
pbb po[N], kp;
int id[N];
pair<int, int> fr[1 << 20][20];
ldb dp[1 << 20][20];
ldb askdis(pbb p1, pbb p2)
{ldb dx = p1.first - p2.first, dy = p1.second - p2.second;return sqrtl(dx * dx + dy * dy);
}
signed main()
{ios::sync_with_stdio(false);cin.tie(nullptr);cout.tie(nullptr);int n, k = 0, rn, con, x, ccn,rk;cin >> n;ldb ky = -1e9, dis;for (int i = 0; i < n; i++){cin >> po[i].first >> po[i].second;id[i] = i + 1;if (po[i].second > ky){k = i;ky = po[i].second;}}rk = id[k];kp = po[k];swap(po[n - 1], po[k]);swap(id[n - 1], id[k]);ccn = n;--n;rn = 1 << n;--rn;for (int i = 0; i <= rn; i++)for (int j = 0; j < n; j++)dp[i][j] = 1e18;for (int i = 0; i < n; i++)dp[1 << i][i] = askdis(kp, po[i]);for (int i = 1; i <= rn; i++)for (int j = 0; j < n; j++){if ((1 << j) & i)continue;con = i | (1 << j);for (int z = 0; z < n; z++){if (!((1 << z) & i))continue;dis = askdis(po[j], po[z]);if (dp[con][j] > dp[i][z] + dis){dp[con][j] = dp[i][z] + dis;fr[con][j] = m_p(i, z);}}}int bestp = 0;for (int i = 0; i < n; i++)if (dp[rn][i] < dp[rn][bestp])bestp = i;con = rn;x = bestp;vector<int> ans;int tc;ans.push_back(id[x]);while (__popcount(con) > 1){tc = fr[con][x].first;x = fr[con][x].second;con = tc;ans.push_back(id[x]);}ans.push_back(rk);for (int i = ans.size() - 1; i >= 0; i--)cout << ans[i] << " ";return 0;
}
这份写得有点丑，因为写的时候比较赶。
