算法练习：多重背包、贪心差分、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.({a, b})) ; 
        f[a + ]--;
        f[b]++;
        mp.({a, b});
    }
     ( i = ; i <= n; i++) {
        f[i] += f[i - ];
        cout << h + f[i] << endl; 
    }
     ;
}