算法练习：多重背包、贪心差分、DFS 及路径 DP 题解

算法练习：多重背包、贪心差分、DFS 及路径 DP 题解

1. Tallest Cow S（最高的奶牛）

题目： P2879 [USACO07JAN] Tallest Cow S

解法：贪心 + 差分

题目要求右端点大于等于左端点，且中间更小，满足要求的最大安排。我们可以贪心地构造，初始让所有的奶牛一样高（最高值已知）。若 a 和 b 之间的高度小于两边，则中间的只少 1。每给一段区间，让中间的区间全部 -1，使用差分数组处理。

最终高度 = 起始最高的高度 + 前缀和处理后的差分数组对应值（变化量）。

特殊处理：

1. 重复数据：会有重复修改区间，需去重。使用 set<pair<int, int>> 存储，帮助去重并标记当前数据是否存过。
2. 大小关系：若 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. 英雄联盟

题目： P5365 [SNOI2017] 英雄联盟

解法：动态规划–多重背包

从前往后挑选皮肤（物品），搭配展示方案数 >= 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++) {
        if (cnt[i] == k) ret++;
    }
    cout << ret << endl;
    return 0;
}

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]

1. c[aim] > c[i], x >= ((i - a) * c[i] - (aim - a) * c[aim]) / (c[aim] - c[i])
2. c[aim] < c[i], x <= ((i - a) * c[i] - (aim - a) * c[aim]) / (c[aim] - c[i])

细节处理： left < x < right。

1. left > right，x 无解；
2. right < 0, left < 0，x 取绝对值较小，值较大的，就是舍（向下取整），用 floor(right)；
3. right > 0, left > 0，x 取绝对值较小，值较小的，就是入（向上取整），用 ceil(left)；
4. 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 if (right < 0) cout << (int)floor(right) << endl;
    else if (right > 0) cout << (int)ceil(left) << endl;
    else cout << 0 << endl;
    return 0;
}

6. 传纸条

题目： P1006 [NOIP 2008 提高组] 传纸条

解法：动态规划–路径类 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 种情况，分别是：

1. 上 + 上，此时的最大和为：f[st - 1][i1 - 1][i2 - 1]；
2. 上 + 左，此时的最大和为：f[st - 1][i1 - 1][i2]；
3. 左 + 上，此时的最大和为：f[st - 1][i1][i2 - 1]；
4. 左 + 左，此时的最大和为：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;
    return 0;
}