注意：这里的题目难度都偏高，主要以蓝色组成，大多不太水，见谅。非蓝色题会特别使用 \(\LaTeX\) 染色。
Notice：这里的类型总结可能会有很大问题。（状态设计优化在本文不算入 dp 优化）
背包 dp
[SCOI2009] 游戏
绝世神仙题，不愧为省选真题。
一次转化
这个对应关系很像有向图，考虑向这个方向转化。
我们发现，这些对应关系就是一个一个的环（包括简单环和自环）。设 \(i\) 点所在的环长为 \(c_i\)，有 \(\sum_{i\in[1,n]} c_i = n\)。
考虑一个初始为 \(1\sim n\) 的点的排列经过转移后回到原状态的步数。显然为 \(\operatorname{lcm}\{c_i\}(i\in[1,n])\)。
那么题意转化为：
构造一个序列 \(a(\sum a_i=n)\)，使其被分为大小为 \([1,|a|]\) 的若干集合后，所有集合内的最小公倍数的可能个数尽可能多。
二次转化
不能再单独只向图的环方向进行转换了，考虑以步数（\(\operatorname{lcm}\)）为突破口。
考虑如何构造出 \(a\) 序列。显然，若要得到最多的 \(\operatorname{lcm}\) 可能个数，可以让每个数都互质。
那么，我们可以构造 \(a_i\) 为一个质数 \(p\) 的 \(k(k\in\mathbb N,p^k\le n)\) 次幂（注意这些质数要互不相同）。
题意遂转化为：你可以选若干个互异质数的 \(k(k\in\mathbb N)\) 次幂，求其总和为 \(n\) 的方案数。（Notice：不选也是一种方案。）
最终转化
显然 \(k\) 可以为 \(0\)，较难处理为一般的 dp。这下这下了。
但是我们考虑 直 接 忽 略。
因为对于任何一种总和 \(<n\) 的构造方法，继续添加若干 \(1\) 后，都会变成 \(n\)。
那么，最终题目就变成这样子：
你可以选若干个互异质数的 \(k(k\in\mathbb N^+)\) 次幂，求其总和为 \(1\sim n\) 的方案数之和。
你会发现：这不就是非常 shabi 的 01 正整数拆分问题？！
\(n\le 1000\)，直接背包即可。时间复杂度 \(O(n^2\log V)\)，其中 \(V\) 为值域，显然与 \(n\) 同阶。
vector<int> p;
// 省去筛法部分；p 是存质数的 vectorint n;
long long dp[1010], ans;int main(){cin >> n;// 记得筛素数dp[0] = 1;for(int i : p){ // ↓ 显然最少得取 1 次幂，即容量不能 <ifor(int j=n; j>=i; --j){for(int k=i; k<=j; k*=i){dp[j] += dp[j - k];}}}for(int i=0; i<=n; ++i){ans += dp[i];}return cout << ans, 0;
}
树形 dp
图上 dp
dp 优化方向
P3120 Cow Hopscotch G（CDQ 分治）
我们要在一个 \(R\times C\)（\(2≤R,C≤750\)）的网格上从左上角跳跃到右下角。每个格子标有 \(1\) 到 \(K\) 的整数（\(1≤K≤R×C\)）。
一次跳跃被定义为合法当且仅当满足以下条件：
1.目标格子的标签数字与当前格子不同；
2.目标格子所在行至少比当前格子多一行；
3.目标格子所在列至少比当前格子多一列。
请计算从左上角到右下角的不同合法跳跃序列总数。
暴力
有一个非常 Naive 的 dp。设 \(dp_{i,j}\) 表示 \((1,1)\) 走到 \((i,j)\) 的方案数。
然后你会发现这玩意是 \(O(R^2C^2)\) 的，非常难以承受。
优化
发现上述转移方程中，\((u,v)\) 能转移到 \((i,j)\) 的条件是：\(u<i, v<j, a_{i,j}\neq a_{u,v}\)。
诶这不是三维偏序吗？
那么我们可以按行（\(i\)）分治，暴力枚举列数，同时计算与这个格子标号相同的格子的 \(dp\) 值然后减掉它，这样就是 \(O(RC\log R)\) 的了。
在核心中，我们要处理 \([l,mid]\) 对 \((mid,r]\) 的 \(dp\) 值的贡献。
具体地，令 \(s_k\) 表示当前转移区间里 \(k = a_{i,j}\) 的转移方法数，\(sum\) 表示当前转移区间里合法的状态之和。那么：
注意，由于 \(u,v\) 要严格小于 \(i,j\)，所以要先更新 \((mid,r]\) 的 dp 值。否则等于时的状态也会被更新。
点击查看代码
using ll = long long;const ll mod = 1000000007;
int n, m, k;
ll dp[757][757], s[751 * 751], a[757][757];void CDQ(int l, int r){if(l == r){return ;}int mid = l+r >> 1; ll sum = 0;CDQ(l, mid);for(int j=1; j<=m; ++j){for(int i = mid+1; i <= r; ++i){dp[i][j] = (dp[i][j] + sum - s[a[i][j]] + mod) % mod;}for(int i=l; i<=mid; ++i){s[a[i][j]] = (s[a[i][j]] + dp[i][j]) % mod;sum = (sum + dp[i][j]) % mod;}}for(int i=l; i<=r; ++i) for(int j=1; j<=m; ++j) s[a[i][j]] = 0;CDQ(mid + 1, r);
}int main(){cin >> n >> m >> k;for(int i=1; i<=n; ++i){for(int j=1; j<=m; ++j){cin >> a[i][j];}}dp[1][1] = 1;CDQ(1, n);cout << (dp[n][m] + mod) % mod;return 0;
}
不知道该算什么的杂项 dp
P3132 Angry Cows（二分 + dp）
有 \(N\) 个整点位于数轴上不同位置 \(x_1,x_2,\dots,x_N\)。如果一个点 \(p\) 被施加了权值 \(R\)，他会传递这个值，覆盖 \([p-R,p+R]\) 范围内的所有点。这些被覆盖的点随后会同时接受 \(R-1\) 的权值并继续传递，覆盖半径为 \(R-1\)。任何尚未被覆盖的点如果被覆盖，则会同时接受 \(R-2\) 的权值并传递，半径为 \(R-2\)，依此类推。
请确定最小的权 \(R\)，使得它在适当的位置可以覆盖所有点。
Analysis
首先，这个答案具有单调性。即若 \(R_1\) 合法，那么 \(R_2(R_2>R_1)\) 一定合法。可以二分答案。
考虑如何 check 这个答案 \(R\)。
可以预处理出 \(f_i\) 和 \(dp_i\)，分别表示 \(i\) 覆盖 \(n\) 和 \(1\) 的最小权值。
我们从大到小遍历点集 \(x\)，若遍历到一个点 \(i\) 可以作为 \(R\) 的半径左端点（\(dp_i\le R-1\)）覆盖左边所有的点，那么直接从当前点向后枚举右端点 \(j\)，直到找到 \(f_j\le R-1\) 即可，不过是平方的。
but，我们又发现：\(dp_i\) 随 \(i\) 的递增而增大，\(f_i\) 随 \(i\) 的递减而增大。
所以，如果第一次枚举右端点失败，那么这个答案是非法的。这样 check 就是 \(O(n)\) 的了。
具体地，如果对于最大的满足 \(dp_i\le R-1\) 的 \(i\)，我们都没有找到 \(j\)，那么根据 \(f_i\) 随 \(i\) 减小而增大的性质，便不可能有 \(f_j\le R-1\) 的 \(j\) 了。
预处理
现在，问题变成了如何求 \(dp_i,f_i\)。（先求 \(dp_i\)，求 \(f_i\) 的只需将枚举点的方向、运算符要改变。）
考虑再枚举第一个不可以被覆盖的点 \(j(j<i)\)。如果 \(a_i-a_j-1>dp_i\)，那么 \(j\) 就覆盖不到了。不过是 \(O(n^2)\) 的。
转移方程为（此处将条件省去）：
考虑优化枚举 \(j\) 的过程。
显然，这个 \(j\) 具有单调性，并且右移操作便捷，考虑用双指针维护。这样 preprogress 就是 \(O(n)\) 的了。
总复杂度 \(O(n\log V)\)，V 为值域。
点击查看代码（请注意仔细阅读注释）
int n;
ll a[50005], dp[50005], f[50005]; // dp_i 表示摧毁 1 的最少能量，f_i 表示摧毁 n 的...。bool check(double R){for(int i=n; i; --i) {if(dp[i] <= R - 1){ // 左边可以全部爆炸for(int j = i; j <= n && a[j] - a[i] <= 2. * R; ++j){if(f[j] <= R - 1){return 1;}} break;}}return 0;
}int main(){n = read();for(int i=1; i<=n; ++i){a[i] = read();}sort(a+1, a+n+1);memset(f, 0x7f, sizeof f);memset(dp, 0x7f, sizeof dp);int h = 1, t = n, ans = 0;dp[1] = f[n] = 0;for(int i=2; i<=n; ++i){while(h + 1 < i && a[i] - a[h+1] > dp[h+1] + 1){++ h; // 从左找找到最后一个 i 可以引爆到的点}dp[i] = min(dp[h + 1] + 1, a[i] - a[h]);}for(int i=n-1; i; --i){while(t - 1 > i && a[t-1] - a[i] > f[t-1] + 1){-- t; // 从右同理}f[i] = min(f[t - 1] + 1, a[t] - a[i]);}double l = 1., r = a[n];while(r - l > 1e-3){ // 求最小的 Rdouble mid = (l+r) / 2.;if(check(mid)){r = mid;} else {l = mid;}}cout << fixed << setprecision(1) << r;return 0;
}