算法练习：多重背包、贪心差分、DFS 及路径 DP 题解
1. Tallest Cow S（最高的奶牛）
题目： P2879 [USACO07JAN] Tallest Cow S
解法：贪心 + 差分
题目要求右端点大于等于左端点，且中间更小，满足要求的最大安排。我们可以贪心地构造，初始让所有的奶牛一样高（最高值已知）。若 a 和 b 之间的高度小于两边，则中间的只少 1。每给一段区间，让中间的区间全部 -1，使用差分数组处理。
最终高度 = 起始最高的高度 + 前缀和处理后的差分数组对应值（变化量）。
特殊处理：
- 重复数据：会有重复修改区间，需去重。使用
set<pair<int, int>>存储，帮助去重并标记当前数据是否存过。 - 大小关系：若
a > b，需交换a和b。
代码：
#include <iostream>
#include <set>
using namespace std;
const int N = 1e4 + 10;
int n, id, h, r;
int f[N]; // 差分数数组
int main() {
cin >> n >> id >> h >> r;
set<pair<int, int>> mp; // 会有重复的修改区间，去重
while (r--) {
int a, b;
cin >> a >> b;
if (a > b) swap(a, b);
// [a + 1, b - 1]
if (mp.count({a, b})) continue; // 重复的不再进行修改
f[a + 1]--;
f[b]++;
mp.insert({a, b});
}
for (int i = 1; i <= n; i++) {
f[i] += f[i - 1];
cout << h + f[i] << endl; // 开始默认都为最大高度 h，然后按题目输入条件修改
}
return 0;
}
2. 英雄联盟
解法：动态规划–多重背包
从前往后挑选皮肤（物品），搭配展示方案数 >= M 的最小花费，且物品数有限制，可想到多重背包问题。
1. 状态表示： 有两种状态表示都能解决问题，但第一种时间和空间会超（第二维最大值 1e17）。因此选择第二种：
f[i][j]表示从前i个英雄中挑选，总花费为j时，此时的最大方案数。 在打表结束后，从前往后扫描最后一行，从f[n][1]开始找出第一个方案数超过 m 的花费为最小，即为结果。
2. 状态转移方程：
根据第 i 个英雄选择皮肤数量分类讨论，假设选了 p 个皮肤，其中 0 <= p <= k[i]，并且 p * c[i] <= j。此时的最大方案数为 f[i - 1][j - p * c[i]] * p。
状态转移方程就是所有合法 k 情况下的最大值。
3. 初始化：
f[0][0] = 1，因为后续方案数是累乘，所以这里初始化为 1 就能保证后续填表是正确的。
代码：
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 300, M = 1e6 + 10;
LL n, m;
LL cnt[N], v[N];
LL f[M];
LL sum; // 最大花费
int main() {
cin >> n >> m;
for (int i = 1; i <= n; i++) cin >> cnt[i];
for (int i = 1; i <= n; i++) {
cin >> v[i];
sum += v[i] * cnt[i];
}
f[0] = 1;
for (int i = 1; i <= n; i++) {
for (int j = sum; j >= 0; j--) {
for (int k = 0; k <= cnt[i] && k * v[i] <= j; k++) {
f[j] = max(f[j], f[j - k * v[i]] * k);
}
}
}
for (int j = 1; j <= sum; j++) {
// 从花费最小的开始找第一个满足要求的
if (f[j] > m) {
cout << j << endl;
break;
}
}
return 0;
}
3. 小 A 的糖果
题目： P3817 小 A 的糖果
解法：贪心
从前往后考虑每个盒子糖果数，如果第 i 个盒子 a[i] + a[i - 1] > x，拿走糖果。
怎么拿？
- 贪心策略：想到拿尽量少且满足要求，即
d = a[i] + a[i - 1] - x。拿前面一个会对与后面的数量和产生影响； - 优化：从第二个开始，把开始前面一个看成 0 个处理。为了让后面相邻元素累加尽可能小，应该从
i位置拿走d的糖果，此时a[i] = a[i] - d，化简完之后为a[i] = x - a[i - 1]。
代码：
#include <iostream>
using namespace std;
typedef long long LL;
const int N = 1e5 + 10;
LL n, x;
LL a[N];
int main() {
cin >> n >> x;
LL sum = 0;
for (int i = 1; i <= n; i++) {
cin >> a[i];
LL d = a[i] + a[i - 1] - x;
if (d > 0) {
sum += d;
a[i] = x - a[i - 1];
}
}
cout << sum << endl;
return 0;
}
4. Cow Picnic S（奶牛野餐）
题目： P2853 [USACO06DEC] Cow Picnic S
解法：dfs/bfs 暴搜
要想每个奶牛都能到达牧场，以（k 个奶牛）每个奶牛的位置为起点做一次 dfs/bfs，标记可以到达的点。哪些结点被标记了 k 次，即为所求结果。
代码：
#include <iostream>
#include <cstring>
#include <vector>
using namespace std;
const int N = 1010;
int k, n, m;
int a[N]; // k 头奶牛的编号
vector<int> edges[N];
int cnt[N];
bool st[N];
void dfs(int u) {
st[u] = true;
cnt[u]++;
for (int v : edges[u]) {
if (!st[v]) dfs(v);
}
}
int main() {
cin >> k >> n >> m;
for (int i = 1; i <= k; i++) cin >> a[i];
for (int i = 1; i <= m; i++) {
int x, y;
cin >> x >> y;
edges[x].push_back(y);
}
for (int i = 1; i <= k; i++) {
memset(st, 0, sizeof st); // 重置更新为 0
dfs(a[i]);
}
int ret = 0;
for (int i = 1; i <= n; i++) {
(cnt[i] == k) ret++;
}
cout << ret << endl;
;
}
5. 税收与补贴问题
题目： P1023 [NOIP 2000 普及组] 税收与补贴问题
解法：数学
设政府干预 x 元。
可列式子： d = (130 - 120) / (30 - 28) = 5。
(28 - 28 + x) * 130 (29 - 28 + x) * 125 (30 - 28 + x) * 120 (31 - 28 + x) * 110 ... (38 - 28 + x) * 5
(31 - 28 + x) * 110 >= (28 - 28 + x) * 130, (29 - 28 + x) * 125, (30 - 28 + x) * 120 分别化为 x <= p1, x <= p2, x <= p3。要想全部都满足，则：x <= min(p1, p2, p3)
(31 - 28 + x) * 110 >= (32 - 28 + x) * 95, (33 - 28 + x) * 80 ... (38 - 28 + x) * 5 分别化为 x >= p4, x >= p5, x >= p6... 要想全部都满足，则：x >= max(p4, p5, p6...)
政府规定价格 aim，成本：a，销量：c[i]，表示售价为 i 时的对应销量。 (aim - a + x) * c[aim] >= (i - a + x) * c[i] (aim - a) * c[aim] + x * c[aim] >= (i - a) * c[i] + x * c[i] x * (c[aim] - c[i]) >= (i - a) * c[i] - (aim - a) * c[aim]
- c[aim] > c[i], x >= ((i - a) * c[i] - (aim - a) * c[aim]) / (c[aim] - c[i])
- c[aim] < c[i], x <= ((i - a) * c[i] - (aim - a) * c[aim]) / (c[aim] - c[i])
细节处理： left < x < right。
- left > right，x 无解；
- right < 0, left < 0，x 取绝对值较小，值较大的，就是舍（向下取整），用 floor(right)；
- right > 0, left > 0，x 取绝对值较小，值较小的，就是入（向上取整），用 ceil(left)；
- left < 0, right > 0，x 取绝对值较小，取 0。
代码：
#include <iostream>
#include <cmath>
using namespace std;
const int N = 1e5 + 10;
int aim, a;
int c[N]; // 售价为 i 时，销量为 c[i]
int main() {
cin >> aim;
int x, y;
cin >> x >> y;
a = x;
c[x] = y;
int prev = x; // 存前一个的定价
while (cin >> x >> y, x != -1 && y != -1) {
int d = (c[prev] - y) / (x - prev);
for (int i = prev + 1, j = c[prev] - d; i <= x; i++, j -= d) {
c[i] = j;
}
prev = x;
}
int d;
cin >> d;
for (int i = prev + 1, j = c[prev] - d; j >= 0; i++, j -= d) {
c[i] = j;
prev = i;
}
double left = -1e9, right = 1e9;
for (int i = a; i <= prev; i++) {
double val = 1.0 * ((i - a) * c[i] - (aim - a) * c[aim]) / (c[aim] - c[i]);
if (c[aim] > c[i]) left = max(left, val);
else if (c[aim] < c[i]) right = min(right, val);
}
if (left > right) cout << "NO SOLUTION" << endl;
else (right < ) cout << ()(right) << endl;
(right > ) cout << ()(left) << endl;
cout << << endl;
;
}
6. 传纸条
解法：动态规划–路径类 dp
类似方格取数，但与方格取数的不同点在于处理相遇点的策略，这里不能有相遇点。
1. 状态表示：
f[st][i1][i2] 表示：第一条路在 [i1, st - i1]，第二条路在 [i2, st - i2] 时，两者的路径最大和。
那我们的最终结果就是 f[n + m][m][m]。
2. 状态转移方程：
第一条路可以从上 [i1 - 1, st - i1] 或者左 [i1, st - i1 - 1] 走到 [i1, st - i1] 位置；第二条路可以从上 [i2 - 1, st - i2] 或者左 [i2, st - i2 - 1] 走到 [i2, st - i2] 位置。排列组合一下一共 4 种情况，分别是：
- 上 + 上，此时的最大和为：
f[st - 1][i1 - 1][i2 - 1]； - 上 + 左，此时的最大和为：
f[st - 1][i1 - 1][i2]； - 左 + 上，此时的最大和为：
f[st - 1][i1][i2 - 1]； - 左 + 左，此时的最大和为：
f[st - 1][i1][i2]； 取上面四种情况的最大值，然后再加上a[i1][j1]和a[i2][j2]。 但是要注意，如果两个路径当前在同一位置时，直接 continue，因为两条路不能走在相同的位置。不过，如果是最后一个格子的话，还是要计算的。
3. 初始化： 算的是路径和，0 不会影响最终结果，直接填表。
4. 填表顺序： 先从小到大循环横纵坐标之和，然后依次从小到大循环两者的横坐标。
代码：
#include <iostream>
using namespace std;
const int N = 55;
int m, n;
int a[N][N];
int f[N + N][N][N];
int main() {
cin >> m >> n;
for (int i = 1; i <= m; i++)
for (int j = 1; j <= n; j++)
cin >> a[i][j];
for (int s = 2; s <= n + m; s++) {
for (int i1 = 1; i1 <= m; i1++) {
for (int i2 = 1; i2 <= m; i2++) {
if (i1 == i2 && s != n + m) continue;
int j1 = s - i1, j2 = s - i2;
if (j1 < 1 || j1 > n || j2 < 1 || j2 > n) continue;
f[s][i1][i2] = max(f[s][i1][i2], f[s - 1][i1 - 1][i2 - 1]);
f[s][i1][i2] = max(f[s][i1][i2], f[s - 1][i1 - 1][i2]);
f[s][i1][i2] = max(f[s][i1][i2], f[s - 1][i1][i2 - 1]);
f[s][i1][i2] = max(f[s][i1][i2], f[s - 1][i1][i2]);
f[s][i1][i2] += a[i1][j1] + a[i2][j2];
}
}
}
cout << f[n + m][m][m] << endl;
;
}
