基础动态规划
例 \(1.1\)：[NOIP2010 提高组] 乌龟棋 - 洛谷
记录 \(f[i][j][k][l]\) 表示每种卡片用的个数即可，距离可以现算。
例 \(1.2\)：[HAOI2006]数字序列 - 洛谷
开始想了个 \(n*\max{a[i]}\) 的屑做法，只有 \(27~\text{pts}\)，评测记录 - 洛谷 。
正解：可以保留 \(a[i]\) 和 \(a[j]\) 的充分必要条件是 \(a[j]-a[i]\ge j-i,(j>=i)\)
移项得 \(a[j]-j\ge a[i]-i\) ，设 \(b[i]=a[i]-i\)，问题一就转化为求 \(b[i]\) 的最长不下降子序列。
对于第二问，设 \(pre_i\) 表示 \(b_i\) 由 \(b_{pre_i}\) 转移而来。
\(\mathrm{Lemma}:\) \(b_i\) 和 \(b_{pre_i}\) 存在一个分界点 \(k\) 满足 \(\forall j\in [b_{pre_i},b_k], b_j=b_{pre_i}\)，\(\forall l\in [b_{k+1},b_i],b_l=b_i\)
证明：
考虑 \(b_{pre_i}\to b_i\) 之间的赋值情况，一定可以被表示为台阶状。
对于 \(cnt_{>b_i} > cnt_{<b_{pre_i}}\)，可以将台阶向上移动到与下一个平齐。
对于 \(cnt_{>b_i}<cnt_{<b_{pre_i}}\)，可以将台阶向下移动到与上一个台阶平齐。
\(Q.E.D\)
枚举每个区间的 \(k\)，即可计算总代价。
具体实现时，给 \(b\) 开头加一个极小值，末尾加一个极大值，即 \(b[0]=-INF, b[n+1]=INF\)
这样，即可对序列 \(b\) 运用上述结论，否则对于 \(b[1]\) 极大或 \(b[n]\) 极小的情况就会出错。
调试惨烈（
例 \(1.3\)：[SCOI2003]字符串折叠 - 洛谷
区间 \(DP\)，\(f[i][j]=\min\left\{f[i][k] + f[k+1][j]\right\}\)
考虑折叠的情况，枚举 \(j-i+1\) 的约数，检验是否可以转移即可。
例 \(1.4\)：[BalticOI 2008]选举 Easy - 洛谷
此题即为 \(\displaystyle S-a_{\min}\le \frac{tot}{2}\) ，设 \(f[i][j]\) 表示在前 \(i\) 个中选择人数和为 \(j\) 的党派是否可行。
设计转移方程为 \(\displaystyle f[i][j] \mid = f[i][j-a[i]]~(j-a[i]\le \frac{tot}{2})\) 。事先将 \(a[i]\) 排序即可满足题意条件：每次取出的 \(a[i]\) 均为最小的。
压掉一维后，时间复杂度为 \(O(nV)\) ，空间复杂度为 \(O(n+V)\) 。
例 \(1.5\)：[SCOI2009]粉刷匠 - 洛谷
设 \(f[i][j]\) 表示前 \(i\) 块木板，粉刷 \(j\) 次的最大正确数，\(G[i][j][k]\) 为第 \(i\) 块模板前 \(j\) 个格子，粉刷 \(k\) 次所能达到的最大正确数。
于是 \(f[i][j]=f[i - 1][j - l] + G[i][m][l]\) ，\(G[i][j][k]=G[i][j-l][k-1]+Calc(l, j)\)，转移即可。
例 \(1.6\)：[CTSC1997] 选课 - 洛谷
题意可以抽象为一个森林。
设 \(f[i][j]\) 表示在以 \(i\) 为根的子树中选出 \(j\) 个能得到的最大学分。
不难发现，满足要求的就是一个与 \(i\) 相连的连通块。
那么考虑前缀和优化：\(f[i][j]=\max\{f[i][k] + f[son][j-k]\}\) 。其中 \(f[i][j]\) 表示已经转移的子树的答案。转移边界即为 \(f[i][1]=val[i]\) 。为防止后效性，交换一下枚举顺序和方向即可。
例 \(1.7\)：[CSP-J2020] 方格取数 - 洛谷
设 \(up[i][j], down[i][j], left[i][j]\) 分别表示从上，下，左到点 \((i,j)\) 的最大点权。因为只能向右不能向左，于是以列为阶段，转移即可。
例 \(1.8\)：ρars/ey - 洛谷
好像考察的是树形背包的上下界优化。不过我不懂，于是由于上下界没卡紧，导致第一次提交 \(70pts\) 。
树形背包很好想，设 \(f[i][j]\) 表示在以 \(i\) 为根的子树内，保留大小为 \(j\) 的块的最小代价，转移即可。
每次均为 \(sz[x] * sz[y]\) 的，可以证明复杂度正确。
找了篇博客，上面有证明。
至于我为什么假了，可以参见 100pts 评测 - 洛谷 和 70pts 评测 - 洛谷 两次提交。
上下界一定要卡紧，最好采用 \(f[i+j]=\dots f[i] + f[j]\) 这种写法，不容易挂上下界。
写的太丑了，重新放一个：评测记录 - 洛谷
例 \(1.9\)：[SCOI2007]压缩 - 洛谷
一开始拿到这道题的时候，以为和 [SCOI2003]字符串折叠 - 洛谷 是一样的。但是仔细思考（WA了两发）后发现，其实是不能嵌套的，因为每个 \(R\) 只会与离他最近的 \(M\) 产生关系。
考虑设 \(dp[i][j][0]\) 表示 \([i,j]\) 之间没有 \(M\) 的最短压缩长度，\(dp[i][j][1]\) 表示 \([i,j]\) 之间有 \(M\) 的最短压缩长度。
\(dp[i][j][0] = \min\{dp[i][k][0]+j-k\}\) 。
\(dp[i][j][1]=\min\{\min(dp[i][k][0],dp[i][k][1])+\min(dp[k+1][r][0],dp[k+1][r][1])+1\}\)
注意到一个 \(M\) 会把原序列分割为互不干扰的两段，于是枚举 \(M\) 的出现位置就得到了 \(dp[i][j][1]\) 的转移方程。
由于 \(i-1\) 位置可以放 \(M\)，于是 \(f[i][j][0]\) 还可以由 \(1+f[i][mid][0]\) 转移得到，\(\mathrm{iff}~s[l\to mid]=s[mid + 1\to r]\) 。
例 \(1.10\)：重建道路 - 洛谷
又是一道树形背包，但是我却足足写了两个小时。
时间主要耗费在了写对拍用的暴力上，屡次对拍，挂的却是暴力，侧面反应代码能力不足。
暴力就应该思维清晰，一发冲过。
例 \(1.11\)：垃圾陷阱 - 洛谷
首先按照时间排序是必须的。
设 \(f[i][j]\) 表示在第 \(i\) 个选择后，还剩 \(j\) 点生命所能达到的最大高度。
有转移 \(f[i][j]=\max(f[i-1][j+delta-duration[i]],t[i-1][j+delta]+height[i])\)
注意转移边界问题。
例 \(1.12\)：[BJOI2019] 排兵布阵 - 洛谷
小清新 \(DP\) 题。设 \(f[i][j]\) 表示考虑前 \(i\) 个城堡，派出 \(j\) 的兵力所能产生的最大收益，排序后转移即可。越来越顺手了呢。
写代码记得检查数组开的范围。
例 \(1.13\)：[ZJOI2007] 时态同步 - 洛谷
将图看成以激发器 \(S\) 为根的一棵树。
可以先若在以 \(S\) 为根的树中时态同步，则在其任意一棵子树中，时态必定也同步。
考虑树形 \(DP\)：设 \(F(x)\) 表示使以 \(x\) 为根的子树时态同步所需的最小次数，\(path(x)\) 表示时态同步时，从 \(x\) 到叶子节点的路径长度。
再设 \(MaxPath\) 表示未经操作时，\(x\) 到叶子节点的最长路径。
容易得出转移方程：\(F(x)=\sum_{son\in x}{F(son)}+\sum_{son\in x}{MaxPath-path(son)-edge(x,son)}\)
完美解决。
标签：洛谷,评测,记录,son,动态,规划,转移,dp From： https://www.cnblogs.com/mklzc/p/16796198.html