可以说是典中典题了。有很多输出方案的方法。
线性 DP
“线性 DP” 不是指线性复杂度，而是指动态规划的每个维度的转移都是线性的。解决这类问题的关键是要确定，在当前维度下，每个状态的求解只与之前的最优解有关。
Mr Young's Picture Permutations
给定一个三角矩阵的形状：有 \(k\) 行，每行左对齐有 \(N_1,N_2,\dots,N_k\) 列，满足 \(N_1\ge N_2\ge\dots\ge N_k\)，且 \(\sum N_i=N\)。将 \(1\) 到 \(N\) 填在这个三角矩阵中，使得每行从左到右递增、每列从上到下递增。求方案数。
\(N\le30,k\le5\)。
注意到 \(k\) 很小，我们可以设一个五维的状态 \(F(x_1,x_2,x_3,x_4,x_5)\)，表示第 \(1\) 到 \(5\) 行分别站了几个人时的方案数。
接下来，我们按 \(1\) 到 \(N\) 的顺序填入。考虑可以填在哪：
- 如果 \(x_1<N_1\)，那么 \(F(x_1+1,x_2,x_3,x_4,x_5)\) 加上 \(F(x_1,x_2,x_3,x_4,x_5)\)；
- 如果 \(x_2<N_2\) 且 \(x_2<x_1\)，那么 \(F(x_1,x_2+1,x_3,x_4,x_5)\) 加上 \(F(x_1,x_2,x_3,x_4,x_5)\)；
- ……（同 \(x_2\)）
时间 \(O(能过)\)（划掉）。
while (cin >> k, k) {
memset(a, 0, sizeof a);
memset(f, 0, sizeof f);
f(i, 1, k) cin >> a[i];
f[0][0][0][0][0] = 1;
f(a1, 0, a[1]) f(a2, 0, a[2]) f(a3, 0, a[3]) f(a4, 0, a[4]) f(a5, 0, a[5]) {
ll t = f[a1][a2][a3][a4][a5];
if (a1 < a[1]) f[a1 + 1][a2][a3][a4][a5] += t;
if (a2 < a[2] && a1 > a2) f[a1][a2 + 1][a3][a4][a5] += t;
if (a3 < a[3] && a2 > a3) f[a1][a2][a3 + 1][a4][a5] += t;
if (a4 < a[4] && a3 > a4) f[a1][a2][a3][a4 + 1][a5] += t;
if (a5 < a[5] && a4 > a5) f[a1][a2][a3][a4][a5 + 1] += t;
}
cout << f[a[1]][a[2]][a[3]][a[4]][a[5]] << '\n';
}
然而这道题是有数学背景的：杨氏矩阵和勾长公式。一些简短的定义：
- （标准）杨氏矩阵（杨表）：即为题目中填完数之后形成的矩阵，即形状是 “阶梯形”、每行每列元素递增。
- 方格 \(v\) 的勾长 \(\operatorname{hook}(v)\)：其同行右侧和同列下侧的方格个数的和，再加 \(1\)（该方格本身）。
利用勾长公式可以直接计算出答案：
\[\dim_{\lambda}=\frac{N!}{\prod_v\operatorname{hook}(v)}. \]while (cin >> k, k) {
ans = 1; n = 0;
memset(h, 0, sizeof h);
f(i, 1, k) cin >> a[i], n += a[i];
f(i, 1, k) f(j, 1, a[i]) {
h[i][j] += a[i] - j;
f(p, 1, i) h[p][j] ++;
}
f(i, 1, k) f(j, 1, a[i]) {
ans *= n--;
ans /= h[i][j]; //尽量边乘边除, 不然小心爆int/ll
}
cout << (ll)round(ans) << '\n';
}
return 0;
*LCIS
求两个数列 \(a,b\)（长度分别为 \(n,m\)）的最长公共上升子序列。输出任意一种解即可。
\(1\le n,m\le500\)，\(0\le a_i,b_i\le10^9\)。
回顾求 LIS 和 LCS 的过程：
- 设 \(f(i,j)\) 表示前 \(i\) 位中以 \(a_j\) 结尾的 LIS 的长度，那么有 \(f(i,j)=\max\limits_{0\le k<j\land a_k<a_j}\{f(i-1,k)\}+1\)，答案为 \(\max f(n,i)\)。
- 设 \(f(i,j)\) 表示 \(a\) 的前 \(i\) 位和 \(b\) 的前 \(j\) 位的 LCS 长度，那么有 \(f(i,j)=\max\begin{cases}f(i-1,j),&\\f(i,j-1),&\\f(i-1,j-1)+1,&\mathrm{if\ }a_i=b_j.\end{cases}\)
我们结合一下，设 \(f(i,j)\) 表示 \(a\) 的前 \(i\) 位和 \(b\) 的前 \(j\) 位构成的、且以 \(b_j\) 结尾的 LCIS 长度。
那么有
\[f(i,j)=\begin{cases}f(i-1,j)&\mathrm{if\ }a_i\ne b_j,\\ \max\limits_{0\le k<j\land b_k<b_j}\{f(i-1,k)\}+1&\mathrm{if\ }a_i=b_j. \end{cases} \]然而再多看一眼就会发现，\(O(n^3)\) 的时间复杂度会爆炸。
发现瓶颈在于求 \(\max\limits_{0\le k<j\land b_k<b_j}\{f(i-1,k)\}\)，我们考虑如何优化。
一个较强的限制条件是 \(b_k<b_j\)，即 \(b_k<a_i\)。考虑 DP 的过程，外层循环的 \(i\) 不变，此时对于所有 \(j\)，能转移的 \(\boldsymbol k\) 的集合都不变，那么接下来要考虑的只有 \(0\le k<j\) 的条件，而这个条件由于内层循环顺序直接自动解决了。因此我们在外层循环中存一个 \(mx\) 表示当前的 \(\max\{f(i-1,k)\}\)，每次转移之后，用 \(f(i-1,j)\) 更新 \(mx\)。
至于输出方案，我们再开一个数组存一下转移路径，最后 DFS 回去即可。时间 \(O(n^2)\)。
vector<int> rec;
void print(int d, int j) {
if (b[j] < 0) return;
rec.push_back(b[j]);
print(d - 1, g[d][j]);
return;
}
signed main() {
cin >> n; f(i, 1, n) cin >> a[i];
cin >> m; f(i, 1, m) cin >> b[i];
a[0] = b[0] = -1;
f(i, 1, n) {
int mx = f[i - 1][0], mxj = 0;
f(j, 1, m) {
if (a[i] == b[j]) f[i][j] = mx + 1, g[i][j] = mxj;
else f[i][j] = f[i - 1][j], g[i][j] = g[i - 1][j];
if (a[i] > b[j] && mx < f[i - 1][j])
mx = f[i - 1][j], mxj = j;
}
}
int ans = 0, ansj = 0;
f(j, 1, m) if (ans < f[n][j])
ans = f[n][j], ansj = j;
cout << ans << '\n';
if (ansj) print(n, ansj);
reverse(rec.begin(), rec.end());
for (int i: rec) cout << i << ' ';
cout << '\n';
return 0;
}
*Making the Grade G
给定长度为 \(n\) 的数列 \(a\)，构造一个长度同样为 \(n\) 的数列 \(b\)，满足：
- \(b\) 非严格单调；
- 最小化 \(S=\sum|a_i-b_i|\)。
求出最小化的 \(S\)。\(1\le n\le2000\)，\(1\le|a_1|\le10^9\)。
\(b\) 可能为非严格单调递增或非严格单调递减，直接正反跑两次就行了。下面只讨论非严格单调递增的情况。
引理 在满足最小化 \(S\) 的情况下，一定存在一种构造 \(b\) 的方案，使得 \(b\) 中的数值都在 \(a\) 中出现过。
证明 考虑数学归纳法。命题对 \(n=1\) 显然成立。设命题对 \(n\ge k-1\)（\(k\ge2\)）成立。当 \(n=k\) 时，我们分情况讨论：
- 若 \(b_{k-1}\le a_k\)，那么令 \(b_k=a_k\)，满足 \(b\) 单调不下降，且 \(S\) 最小，命题成立；
- 若 \(b_{k-1}>a_k\)，则令 \(b_k=b_{k-1}\)。满足 \(b\) 单调不下降。那么 \(S\) 为什么最小呢？设 \(b_j=b_{j+1}=\dots=b_{k-1}=b_k=v\)，设 \(a_j,a_{j+1},\dots,a_{k-1},a_k\) 的中位数为 \(m\)。若 \(m\ge b_{j-1}\)，那么令 \(v=m\)，这样差的绝对值的和最小；否则，令 \(v=b_{j-1}\)，这样所构造的这段 \(b\) 离对应的 \(a\) 最近。
因此，\(b_k\) 一定在 \(a\) 中出现过。证毕。
仿照 LIS，我们设 \(f(i,j)\) 表示完成前 \(i\) 项的构造、且 \(b_i=a_j\) 时的 \(S\)。那么有
\[f(i,j)=\min_{a_k\le a_j}\{f(i-1,k)\}+|a_i-a_j|. \]注意到这个转移方程可以拆成两项。前一项与 \(j\) 有关，由于每次改变 \(i\)，\(j\) 都是相同的，因此前一项在第一维为 \(i-1\) 时可以提前处理出来。而后一项只与 \(i,j\) 有关。综上，我们可以做到 \(O(1)\) 转移，而不必每次寻找 \(\min\)。
总时间复杂度 \(O(n^2)\)。
有一个 \(O(n\log n)\) 的优先队列做法，证明方法似乎是维护下凸壳，然而我根本看不懂 = =||。参见 P4597 序列 sequence 题解区。（@dbxxx 说贪心证法是假的。）
顺便滚动一下数组。
void solve() {
sort(c + 1, c + n + 1);
int t = 0;
f(i, 1, n) {
t ^= 1;
memset(minf[t], 0x3f, sizeof minf[t]);
f(j, 1, n) {
f[t][j] = minf[t ^ 1][j] + abs(a[i] - c[j]);
minf[t][j] = min(f[t][j], minf[t][j - 1]);
}
}
f(j, 1, n) ans = min(ans, f[t][j]);
return;
}
signed main() {
cin >> n;
f(i, 1, n) cin >> a[i], c[i] = a[i];
solve();
reverse(a + 1, a + n + 1); //反着再跑一遍
memset(f, 0, sizeof f);
memset(minf, 0, sizeof minf);
solve();
cout << ans << '\n';
return 0;
}
另外，还有一个套路的 trick：
- 把一个严格单调递增的数列 \(a\) 映射成非严格单调递增的数列 \(a'\)：令 \(a'(i)=a(i)-i\)。
Mobile Service
有一个公司有三个流动员工。每次只有一名员工可以移动，不允许同一位置上同时有两个及以上员工。
每次移动需要花费，从位置 \(p\) 移动到位置 \(q\) 需要花费 \(c(p,q)\) 的价钱。不移动不需要花费（即 \(c(i,i)=0\)），但不保证 \(c(p,q)=c(q,p)\)。
现在给出 \(N\) 个请求，第 \(i\) 个请求发生在位置 \(p_i\)。公司必须按照顺序，派一名员工到位置 \(p_i\)，过程中不能去其他地方，也就是必须直接过去。
三个流动员工的初始位置分别为 \(1,2,3\)。求公司的最小花费。
对于 \(100\%\) 的数据满足 \(3\le L\le200\)，\(1\le N\le100\)，\(0\le c(i,j)\le2000\)。
（输出路径且 256 MB 版：SPOJ SERVICEH - Mobile Service Hard；输出路径且 64 MB 版：P7685 [CEOI2005] Mobile Service。）
员工数量很少，我们可以直接表示他们的状态。而阶段也很好设，就是当前完成了几个请求。
设 \(f(i,x,y,z)\) 表示刚完成第 \(i\) 个请求，三个员工分别在 \(x,y,z\) 处的最小花费。
然而这样设的话，会有冗余的信息：既然刚完成第 \(i\) 个请求，那么一定有一个员工在 \(p_i\) 处。并且，我们并不关心具体是哪个员工在哪个位置，而是关心三个员工所在位置的无序集合。
设 \(f(i,x,y)\) 表示刚完成第 \(i\) 个请求，三个员工分别在 \(x,y,p_i\) 处的最小花费。考虑 \(f(i,x,y)\) 三个员工的贡献，写出状态转移方程：
\[\begin{aligned} f(i+1,x,y)\gets\min\{f(i+1,x,y),f(i,x,y)+c(p_i,p_{i+1})\},\\ f(i+1,p_i,y)\gets\min\{f(i+1,p_i,y),f(i,x,y)+c(x,p_{i+1})\},\\ f(i+1,x,p_i)\gets\min\{f(i+1,x,p_i),f(i,x,y)+c(y,p_{i+1})\}. \end{aligned} \]为了方便，不妨设 \(p_0=3\)，那么初值为 \(f(0,1,2)=0\)，答案为 \(\min\limits_{x,y}f(n,x,y)\)。
顺便滚动一下数组。
cin >> l >> n;
memset(c, 0x3f, sizeof c);
f(i, 1, l) {
c[i][i] = 0;
f(j, 1, l) cin >> c[i][j];
}
f(i, 1, n) cin >> p[i];
memset(f, 0x3f, sizeof f);
f[0][1][2] = 0;
p[0] = 3;
int t = 1;
f(i, 0, n - 1) {
t ^= 1;
memset(f[t^1], 0x3f, sizeof f[t^1]);
f(x, 1, l) {
f(y, 1, l) {
int z = p[i], u = p[i+1];
if (x == y || x == z || y == z) continue;
f[t^1][x][y] = min(f[t^1][x][y], f[t][x][y] + c[z][u]);
f[t^1][x][z] = min(f[t^1][x][z], f[t][x][y] + c[y][u]);
f[t^1][z][y] = min(f[t^1][z][y], f[t][x][y] + c[x][u]);
}
}
}
t ^= 1;
f(x, 1, l) f(y, 1, l) ans = min(ans, f[t][x][y]);
cout << ans << '\n';
传纸条
给定一个 \(N\times M\) 的矩阵 \(A\)，每个格子中有一个整数。现在需要找到两条从左上角 \((1,1)\) 到右下角 \((N,M)\) 的路径，路径上的每一步只能向右或向下走。路径经过的格子中的数会被取走，若两条路径同时经过一个格子，只算一次。求取得的数之和最大是多少。
\(N,M\le50\)。
首先 DP 状态一定是要包含走的步数 \(i\) 的（设在 \((1,1)\) 时是第 \(1\) 步）。对于这种方格里向右或向下走的题，有一个常用的等式：
\[x+y=i+1. \]因此设 \(f(i,x_1,x_2)\) 表示步数为 \(i\)，第一条路径走到 \((x_1,i+1-x_1)\)，第二条路径走到 \((x_2,i+1-x_2)\) 的答案。那么有
\[f(i,x_1,x_2)\gets\max\begin{cases} f(i-1,x_1,x_2),\\ f(i-1,x_1-1,x_2),\\ f(i-1,x_1,x_2-1),\\ f(i-1,x_1-1,x_2-1) \end{cases}+a_{x_1,i+1-x_1}+a_{x_2,i+1-x_2}\times[x_1\ne x_2]. \]初值 \(f(1,1,1)=0\)，答案 \(f(n+m-1,n,n)\)。
顺便滚动一下数组。注意，为了满足无后效性，\(x_1,x_2\) 要倒序枚举。
cin >> n >> m;
f(i, 1, n) f(j, 1, m) cin >> a[i][j];
f(i, 2, n + m - 1) {
int _ = min(i, n);
g(x1, _, 1) {
int y1 = i + 1 - x1;
g(x2, _, 1) {
int &t = f[x1][x2];
int y2 = i + 1 - x2;
if (y1 < 1 || y2 < 1) continue;
t = max(t, f[x1 - 1][x2]);
t = max(t, f[x1][x2 - 1]);
t = max(t, f[x1 - 1][x2 - 1]);
t += a[x1][y1] + (x1 != x2) * a[x2][y2];
}
}
}
cout << f[n][n] << '\n';
*I-country
AcWing 276 | CH 5104 | SGU167 on Codeforces
在 \(N\times M\) 的矩阵中，每个格子有一个权值，要求寻找一个包含 \(K\) 个格子的凸连通块（连通块中间没有空缺，并且轮廓是凸的，如图所示），使这个连通块中的格子的权值和最大。求出这个最大的权值和，并给出连通块的具体方案。
\(N,M\le15\)，\(K\le N\times M\)。每个数字都在 \(0\) 到 \(1000\) 的范围内。
一道状态设计非常神奇的题。
设第 \(i\) 行选中的格子范围为 \([l_i,r_i]\)，共有 \(m\) 行，可以发现，一定存在 \(p,q\) 满足
\[\begin{aligned} l_1\ge\dots\ge l_{p-1}\ge l_p\le l_{p+1}\le\dots\le l_m,\\ r_1\le\dots\le r_{p-1}\le r_p\ge r_{p+1}\ge\dots\ge r_m. \end{aligned} \]即左端点先递减后递增，右端点先递增后递减。（非严格）
我们以行为阶段进行转移。为了确定这一行都可以选哪些格子，我们需要知道：
- 目前为止共选了几个格子；
- 上一行选了哪些格子；
- 左端点目前是递增还是递减；
- 右端点目前是递增还是递减。
设 \(f(i,j,l,r,x,y)\) 表示当前在第 \(i\) 行，目前为止一共选了 \(j\) 个格子，上一行选了 \([l,r]\)，左右端点目前递增 / 递减状态分别是 \(x,y\) 的答案，其中 \(x\) 或 \(y\) 等于 \(0\) 表示递增，\(1\) 表示递减。
分类讨论：
-
左递减、右递增，即左、右均扩张：
需要考虑刚开始的情况，即 \(j=r-l+1\) 的情况，第 \(i\) 行即为开始选的第一行。
\[f(i,j,l,r,1,0)=\sum_{k=l}^ra_{i,k}+\begin{cases} f(i-1,0,0,0,1,0), & \mathrm{if\ }j=r-l+1,\\ \max\limits_{l\le p\le q\le r}\{f(i-1,j-(r-l+1),p,q,1,0)\} & \mathrm{if\ }j>r-l+1. \end{cases} \] -
左递增、右递增，即左收缩、右扩张：
讨论上一行的左端点是扩张还是收缩。
注意，枚举 \(p,q\) 时，由于必须连通，所以要保证 \(l\le q\)。
\[f(i,j,l,r,0,0)=\sum_{k=l}^ra_{i,k}+\max_{1\le p\le l\le q\le r}\left\{\max_{0\le x\le1}f(i-1,j-(r-l+1),p,q,x,0)\right\}. \] -
左递减、右递减，即左扩张、右收缩：
讨论上一行的右端点是扩张还是收缩。
同样，要保证 \(r\le p\)。
\[f(i,j,l,r,1,1)=\sum_{k=l}^ra_{i,k}+\max_{l\le p\le r\le q\le n}\left\{\max_{0\le y\le1}f(i-1,j-(r-l+1),p,q,1,y)\right\}. \] -
左递增、右递减，即左、右均收缩：
讨论上一行的左、右端点是扩张还是收缩。
\[f(i,j,l,r,0,1)=\sum_{k=l}^ra_{i,k}+\max_{1\le p\le l,r\le q\le n}\left\{\max_{0\le x,y\le 1}f(i-1,j-(r-l+1),p,q,x,y)\right\}. \]
初值：\(f(i,0,0,0,1,0)=0\)，答案 \(\max\{f(i,K,l,r,x,y)\}\)。
时间 \(O(nm^4k)\)，设 \(n,m\) 同阶、\(n^2,m^2,k\) 同阶，则时间复杂度为 \(O(n^7)\)。
对于输出方案，再开一个六元组的数组记录每一个状态是从哪个状态转移过来的，最后从答案递归回去即可。
const int N = 16;
int n, m, k, a[N][N], f[N][N * N][N][N][2][2], ans;
struct State {
int i, j, l, r, x, y;
} g[N][N * N][N][N][2][2], state;
signed main() {
cin >> n >> m >> k;
f(i, 1, n) f(j, 1, m) cin >> a[i][j], a[i][j] += a[i][j - 1];
f(i, 1, n) f(j, 0, k) f(l, 1, m) f(r, l, m) {
if (j < r - l + 1) continue;
// 1. 左扩张, 右扩张
{
auto &vf = f[i][j][l][r][1][0];
auto &vg = g[i][j][l][r][1][0];
f(p, l, r) f(q, p, r) {
int val = f[i - 1][j - (r - l + 1)][p][q][1][0];
if (vf < val) {
vf = val;
vg = {i - 1, j - (r - l + 1), p, q, 1, 0};
}
}
vf += a[i][r] - a[i][l - 1];
}
// 2. 左扩张, 右收缩
{
auto &vf = f[i][j][l][r][1][1];
auto &vg = g[i][j][l][r][1][1];
f(p, l, r) f(q, r, m) f(y, 0, 1) {
int val = f[i - 1][j - (r - l + 1)][p][q][1][y];
if (vf < val) {
vf = val;
vg = {i - 1, j - (r - l + 1), p, q, 1, y};
}
}
vf += a[i][r] - a[i][l - 1];
}
// 3. 左收缩, 右扩张
{
auto &vf = f[i][j][l][r][0][0];
auto &vg = g[i][j][l][r][0][0];
f(p, 1, l) f(q, l, r) f(x, 0, 1) {
int val = f[i - 1][j - (r - l + 1)][p][q][x][0];
if (vf < val) {
vf = val;
vg = {i - 1, j - (r - l + 1), p, q, x, 0};
}
}
vf += a[i][r] - a[i][l - 1];
}
// 4. 左收缩, 右收缩
{
auto &vf = f[i][j][l][r][0][1];
auto &vg = g[i][j][l][r][0][1];
f(p, 1, l) f(q, r, m) f(x, 0, 1) f(y, 0, 1) {
int val = f[i - 1][j - (r - l + 1)][p][q][x][y];
if (vf < val) {
vf = val;
vg = {i - 1, j - (r - l + 1), p, q, x, y};
}
}
vf += a[i][r] - a[i][l - 1];
}
}
f(i, 1, n) f(l, 1, m) f(r, l, m) f(x, 0, 1) f(y, 0, 1) {
int val = f[i][k][l][r][x][y];
if (ans < val) {
ans = val;
state = {i, k, l, r, x, y};
}
}
cout << "Oil : " << ans << '\n';
while (state.j) {
f(i, state.l, state.r) cout << state.i << ' ' << i << '\n';
state = g[state.i][state.j][state.l][state.r][state.x][state.y];
}
return 0;
}
*Cookies
圣诞老人共有 \(M\) 个饼干，准备全部分给 \(N\) 个孩子。每个孩子有一个贪婪度，第 \(i\) 个孩子的贪婪度为 \(g_i\)。如果有 \(a_i\) 个孩子拿到的饼干数比第 \(i\) 个孩子多，那么第 \(i\) 个孩子会产生 \(g_i\times a_i\) 的怨气。给定 \(N,M\) 和序列 \(g\)，圣诞老人请你帮他安排一种分配方式，使得每个孩子至少分到一块饼干，并且所有孩子的怨气总和最小。
\(1\le N\le30\)，\(N\le M\le5000\)。
首先这个题看起来就很贪心。感性理解一下，我们猜想，每个孩子拿到的饼干数量随贪婪度递减而递减。
考虑用调整法证明：设 \(g_i>g_j\)。若 \(i\) 比 \(j\) 拿的多，那么这一对的代价为 \(g_j\)，否则，代价为 \(g_i\)。因此 \(i\) 比 \(j\) 拿的多更优。
然而，每个人究竟该拿多少呢？接下来我们用 DP 解决这个问题。
将孩子按照 \(g\) 从大到小排序。设 \(f(i,j)\) 表示前 \(i\) 个孩子一共分了 \(j\) 块饼干的答案。
设孩子 \(i\) 拿了 \(c_i\) 个饼干。转移有两种情况：
- 若 \(c_{i+1}<c_i\)：\(a_{i+1}=i\)；
- 若 \(c_{i+1}=c_i\)：\(a_{i+1}\) 为 \(i\) 减去 \(a_{i+1}\) 前面与 \(a_i\) 相等的连续段的长度。
因此我们需要知道 \(c_i\) 的值才能转移。
画出 \(c\) 的图象是这样的：
神奇的一步来了：观察图中的形状，我们不妨对转移做一个等价转换。
- 若 \(c_i>1\)，那么等价于从 \(1\) 到 \(i\) 的所有人少拿一块饼干，相对大小不变，所以 \(a\) 不变；
- 若 \(c_i=1\)，那么枚举 \(i\) 前面有几个人和 \(i\) 一样拿了 \(1\) 个饼干，然后进行转移。
如下图：
于是，枚举 \(k\) 表示从 \(k+1\) 到 \(i\) 都拿了 \(1\) 个，那么有：
\[f(i,j)=\min\begin{cases}f(i,j-i),\\ \min\limits_{0\le k<i}\left\{f(k,j-(i-k))+k\times\sum\limits_{p=k+1}^ig_p\right\}.\end{cases} \]初值：\(f(0,0)=0\)，答案：\(f(n,m)\)。
本题还要求输出 \(c\)。首先 DP 一遍，并且记录如何转移，然后再复现一遍，同时统计 \(c\) 数组。
int n, m, g[33], f[33][5010], ans[33], id[33]; //g: 原g数组的前缀和
pii rec[33][5010];
inline bool cmp1(int const &p, int const &q) { return g[p] > g[q]; }
inline bool cmp2(int const &p, int const &q) { return p > q; }
void get_ans(int i, int j) {
if (!i) return;
get_ans(rec[i][j].first, rec[i][j].second);
if (rec[i][j].first == i)
f(k, 1, i) ++ans[id[k]];
else f(k, rec[i][j].first + 1, i) ++ans[id[k]];
return;
}
signed main() {
cin >> n >> m;
f(i, 1, n) cin >> g[i], id[i] = i;
sort(id + 1, id + n + 1, cmp1);
sort(g + 1, g + n + 1, cmp2);
f(i, 2, n) g[i] += g[i - 1];
memset(f, 0x3f, sizeof f);
f[0][0] = 0;
f(i, 1, n) {
f(j, i, m) {
f[i][j] = f[i][j - i];
rec[i][j] = (pii){i, j - i};
f(k, 0, i - 1) {
int val = f[k][j - (i - k)] + k * (g[i] - g[k]);
if (f[i][j] > val) {
f[i][j] = val;
rec[i][j] = (pii){k, j - (i - k)};
}
}
}
}
cout << f[n][m] << '\n';
get_ans(n, m);
f(i, 1, n) cout << ans[i] << ' ';
cout << '\n';
return 0;
}
这道题启发我们：
- 可以利用贪心思想或其他算法，来确定 DP 的阶段的顺序。
- 有时找到一个状态的等效状态，可以大大减少需要转移的状态。
背包
背包是线性 DP 中一类重要而特殊的模型。
0/1 背包模型
给定 \(N\) 个物品，其中第 \(i\) 个物品的体积为 \(V_i\)，价值为 \(W_i\)。有一容积为 \(M\) 的背包，要求选择一些物品放入背包，使得物品总体积不超过 \(M\) 的前提下，物品的价值总和最大。
设 \(f(i,j)\) 表示：从前 \(i\) 个物品中选出了总体积为 \(j\) 的物品放入背包，物品的最大价值总和。转移方程：
\[f(i,j)=\max\begin{cases}f(i-1,j),\\ f(i-1,j-V_i)+W_i, & \mathrm{if\ }j\ge V_i. \end{cases} \]初值 \(f(0,0)=0\)，其他为负无穷。答案 \(\max_jf(n,j)\)。
滚动数组后，为了满足无后效性，需要倒序枚举 \(j\)。
int f[M];
memset(f, 0xc0, f);
f[0] = 0;
f(i, 1, n) g(j, m, v[i])
f[j] = max(f[j], f[j - v[i]] + w[i]);
int ans = 0;
f(j, 0, m) ans = max(ans, f[j]);
统计装物品的方案数：设 \(f(i,j)\) 表示方案数。转移方程：
\[f(i,j)=f(i-1,j)+f(i-1,j-v_i). \]初值 \(f(0,0)=1\)，其他为 \(0\)。答案为 \(f(n,m)\)。当然也可以滚动数组。
int f[M];
memset(f, 0, sizeof f);
f[0] = 1;
f(i, 1, n) g(j, m, v[i])
f[j] += f[j - v[i]];
ans = f[m];
Jury Compromise
在一个遥远的国家，一名嫌疑犯是否有罪需要由陪审团来决定。陪审团是由法官从公民中挑选的。
法官先随机挑选 \(N\) 个人（编号 \(1,2…,N\)）作为陪审团的候选人，然后再从这 \(N\) 个人中按照下列方法选出 \(M\) 人组成陪审团。
首先，参与诉讼的控方和辩方会给所有候选人打分，分值在 \(0\) 到 \(20\) 之间，第 \(i\) 个人的得分分别记为 \(p_i\) 和 \(d_i\)。
为了公平起见，法官选出的 \(M\) 个人必须满足：辩方总分 \(D\) 和控方总分 \(P\) 的差的绝对值 \(|D-P|\) 最小。
如果选择方法不唯一，那么再从中选择辨控双方总分之和 \(D+P\) 最大的方案。
求最终的陪审团获得的辩方总分 \(D\)、控方总分 \(P\)，以及陪审团人选的编号。
注意：若陪审团的人选方案不唯一，则任意输出一组合法方案即可。
\(1\le N\le200\)，\(1\le M\le20\)。
每个人有三个 ”体积维度“：
- 人数，为 \(1\)；
- 辩方打分，为 \(d_i\)，范围 \(0\) 到 \(20\)；
- 控方打分，为 \(p_i\)，范围 \(0\) 到 \(20\)。
直接地，设布尔数组 \(f(i,j,d,p)\) 表示前 \(i\) 人中选了 \(j\) 人，辩方总分为 \(d\)，控方总分为 \(p\) 是否可行，即方案是否存在。那么有
\[f(i,j,d,p)=f(i-1,j,d,p)\mathrm{\ or\ }f(i-1,j-1,d-d_i,p-p_i). \]初值：\(f(0,0,0,0)=\mathrm{true}\)，其余为 \(\mathrm{false}\)。目标：找到 \(f(N,M,d,p)\) 满足 \(f(N,M,d,p)=\mathrm{true}\) 且 \(|d-p|\) 最小、\(|d-p|\) 相同的 \(d+p\) 最大。时间复杂度 \(O(N^4\times d\times p)\)，显然会超时。
我们可以换个思路。既然题目要求的是 \(|D-P|\) 最小、\(D+P\) 最大，我们不如把 \(d_i-p_i\) 设为除了人数之外的另一维体积，\(d_i+p_i\) 设为价值，最后从小到大枚举背包的这一维的总体积（的绝对值），如果有解则为答案。
具体地，设 \(f(i,j,k)\) 表示已经在前 \(i\) 个候选人中选了 \(j\) 个，且此时辩方总分和控方总分的差为 \(k\) 时，辩方总分和控方总分的和的最大值。那么有：
\[f(i,j,k)=\max\{f(i-1,j,k),f(i-1,j-1,k-(p_i-d_i))+p_i+d_i\}. \]初值：\(f(0,0)=0\)，其他为负无穷。目标：找到 \(f(N,M,k)\)，使得 \(|k|\) 最小，\(|k|\) 相同时 \(f(N,M,k)\) 最大。
滚动第一维，对第二维倒序循环，即可满足无后效性（不用所有维都倒序循环）。
另外，\(f\) 的第三维可能为负数，为了避免负数下标，我们将这一维整个平移，平移距离 \(400\) 就够了。
时间 \(O(nmk)\)，\(k=800\)。
#include <iostream>
#include <cstring>
#include <vector>
#define f(x, y, z) for (int x = (y); (x) <= (z); ++(x))
#define g(x, y, z) for (int x = (y); (x) >= (z); --(x))
using namespace std;
const int N = 210;
const int base = 400;
int n, m, a[N], b[N], f[22][810], g[N][22][820], ans, suma, sumb;
vector<int> rec;
void get_ans(int i, int j, int k) {
if (!j)
return;
int lst = g[i][j][k];
get_ans(lst - 1, j - 1, k - (a[lst] - b[lst]));
rec.push_back(lst);
suma += a[lst], sumb += b[lst];
return;
}
signed main() {
cin >> n >> m;
f(i, 1, n) cin >> a[i] >> b[i];
memset(f, 0xc0, sizeof f);
f[0][base] = 0;
f(i, 1, n) {
memcpy(g[i], g[i - 1], sizeof(g[i - 1]));
g(j, m, 1) {
int low = max(a[i] - b[i], 0), high = min(a[i] - b[i] + 800, 800);
f(k, low, high) {
int val = f[j - 1][k - (a[i] - b[i])] + a[i] + b[i];
if (f[j][k] < val) {
f[j][k] = val;
g[i][j][k] = i;
}
}
}
}
f(k, 0, 400) {
if (f[m][base + k] >= 0 && f[m][base + k] >= f[m][base - k]) {
ans = base + k;
break;
}
if (f[m][base - k] >= 0) {
ans = base - k;
break;
}
}
get_ans(n, m, ans);
cout << "Best jury has value " << suma << " for prosecution and value " << sumb << " for defence:\n";
for (int i : rec) cout << i << ' ';
cout << '\n';
return 0;
}
完全背包模型
给定 \(N\) 种物品，其中第 \(i\) 种物品的体积为 \(V_i\)，价值为 \(W_i\)，并且有无数个。有一容积为 \(M\) 的背包，要求选择一些物品放入背包，使得物品总体积不超过 \(M\) 的前提下，物品的价值总和最大。
同样，设 \(f(i,j)\) 表示：从前 \(i\) 个物品中选出了总体积为 \(j\) 的物品放入背包，物品的最大价值总和。
讨论之前是否考虑选过第 \(i\) 种物品。转移方程：
\[f(i,j)=\max\begin{cases}f(i-1,j),\\ f(i,j-V_i)+W_i, & \mathrm{if\ }j\ge V_i. \end{cases} \]初值 \(f(0,0)=0\)，其他为负无穷。答案 \(\max_jf(n,j)\)。
由于转移方程中的第二种情况是在同一阶段中转移，即 \(i\) 相同，因此滚动数组后正序枚举 \(j\) 正好可以转移。换句话说，正序枚举 \(j\) 的意义即为物品可以用无数次（只要不超过 \(M\)）。
int f[M];
memset(f, 0xc0, sizeof f);
f[0] = 0;
f(i, 1, n) f(j, v[i], m)
f[j] = max(f[j], f[j - v[i]] + w[i]);
int ans = 0;
f(j, 0, m) ans = max(ans, f[j]);
同样，改造一下就可以变成求方案数的代码：
int f[M];
memset(f, 0, sizeof f);
f[0] = 1;
f(i, 1, n) f(j, v[i], m)
f[j] += f[j - v[i]] + w[i];
ans = f[m];
多重背包模型
给定 \(N\) 种物品，其中第 \(i\) 种物品的体积为 \(V_i\)，价值为 \(W_i\)，并且有 \(C_i\) 个。有一容积为 \(M\) 的背包，要求选择一些物品放入背包，使得物品总体积不超过 \(M\) 的前提下，物品的价值总和最大。
直接拆分法
把第 \(i\) 种物品看成独立的 \(C_i\) 个物品，转化为 0/1 背包。物品总数为 \(\sum_{i=1}^NC_i\)，时间复杂度 \(O\left(M\times\sum_{i=1}^NC_i\right)\)，一般是无法承受的。
二进制拆分法
考虑一个十进制数转成二进制数的过程。设二进制共有 \(k\) 位，那么从 \(2^0,2^1,\dots,2^{k-1}\) 这 \(k\) 个 \(2\) 的整数次幂中选出若干个相加，可以得到 \([0,2^k-1]\) 内的任意一个整数。因此，进一步地，设 \(p\) 为使得 \(2^0+2^1+\dots+2^p\le C_i\) 的最大整数 \(p\)，设余数
\[R_i=C_i-(2^0+2^1+\dots+2^p)=C_i-2^{p+1}+1. \]那么 \(2^0,2^1,\dots,2^p,R_i\) 可以凑成 \([0,C_i]\) 内的任意一个整数。
综上所述，我们可以把数量为 \(C_i\) 的第 \(i\) 种物品拆成 \(p+2\) 个物品，其体积分别为：
\[2^0\times V_i,2^1\times V_i,\dots,2^p\times V_i,R_i\times V_i. \]时间 \(O\left(M\times\sum_{i=1}^N\log C_i\right)\)，效率较高。
单调队列优化
时间 \(O(NM)\)，与一般的 0/1 背包和完全背包相同。简神！
Coins
标签：指南,le,进阶,val,int,max,cin,ans,动态 From： https://www.cnblogs.com/f2021ljh/p/17446720.html给定 \(N\) 种硬币，其中第 \(i\) 种硬币的面值为 \(A_i\)，共有 \(C_i\) 个。
从中选出若干个硬币，把面值相加，若结果为 \(S\)，则称 “面值 \(S\) 能被拼成”。
求 \(1\) 到 \(M\) 之间能被拼成的面值有多少个。
\(1\le N\le100\)，\(1\le M\le10^5\)，\(1\le A_i\le10^5\)，\(1\le C_i\le1000\)。