USACO 2019 Platinum Greedy Pie Eaters 题解

题目分析

这道题要求选择一组奶牛序列，使得按顺序吃派时每头奶牛都能吃到至少一个喜欢的派，并且最大化这些奶牛的体重和。

关键约束：

• 奶牛按顺序吃派，每头奶牛会吃掉她喜欢范围内所有剩余的派
• 必须保证轮到每头奶牛时，她喜欢的派中至少还有一个没被吃掉
• 没有两头奶牛喜欢相同范围的派

解题思路

核心观察

1. 区间覆盖性质：每头奶牛对应一个区间 $[l_i, r_i]$，吃派时会清空该区间
2. 顺序重要性：奶牛吃派的顺序影响后续奶牛能否吃到派
3. 区间DP：由于 $N \leq 300$，可以使用区间动态规划

算法设计

代码采用了预处理 + 区间DP的方法：

主要步骤：

1. 预处理：对于每个位置和区间，记录该区间内能选择的最大体重奶牛
2. 区间DP：计算每个区间 $[i,j]$ 能获得的最大体重和

代码详解

#include <bits/stdc++.h>
#define ll long long
#define F(i,l,r) for(ll i=l;i<=r;i++)
using namespace std;

ll n, m, f[305][305];
int g[305][305][305];

int main() {
    cin >> n >> m;
    
    // 步骤1: 读入数据并初始化
    F(i, 1, m) {
        int l, r, x;
        cin >> x >> l >> r;
        // 对于区间[l,r]内的每个位置j，记录可能的最大体重
        F(j, l, r) 
            g[j][l][r] = max(g[j][l][r], x);
    }
    
    // 步骤2: 预处理区间最大值
    F(i, 1, n) for (ll l = n; l; l--)
        F(r, l, n)
            // g[i][l][r] 表示在区间[l,r]中包含位置i的奶牛的最大体重
            g[i][l][r] = max({g[i][l][r], g[i][l+1][r], g[i][l][r-1]});
    
    // 步骤3: 区间动态规划
    for (ll i = n; i; i--)  // 区间左端点从后往前
        F(j, i, n) {        // 区间右端点
            // 初始值：继承子区间
            f[i][j] = max(f[i+1][j], f[i][j-1]);
            
            // 枚举分割点k，考虑选择包含位置k的奶牛
            F(k, i, j)
                f[i][j] = max(f[i][j], 
                    f[i][k-1] + g[k][i][j] + f[k+1][j]);
        }
    
    cout << f[1][n];
    return 0;
}

算法原理详解

1. 预处理阶段

g[k][l][r] 的含义：在区间 $[l, r]$ 中，必须包含位置 k 的奶牛的最大体重。

预处理过程：

• 首先读入每头奶牛的信息，更新对应的三维数组
• 然后通过递推计算区间最大值：

  g[i][l][r] = max(g[i][l][r], g[i][l+1][r], g[i][l][r-1])
  

  这表示区间 $[l,r]$ 中包含位置 $i$ 的最大体重，可以从子区间 $[l+1,r]$ 和 $[l,r-1]$ 继承。

2. 动态规划状态

f[i][j] 表示在派区间 $[i, j]$ 上能获得的最大体重和。

3. 状态转移

对于区间 $[i, j]$，有三种情况：

1. 不选择左端点：f[i][j] = f[i+1][j]

2. 不选择右端点：f[i][j] = f[i][j-1]

3. 选择包含位置 k 的奶牛：

   f[i][j] = f[i][k-1] + g[k][i][j] + f[k+1][j]
   

   这里：

   • f[i][k-1]：区间 $[i, k-1]$ 的最大和
   • g[k][i][j]：在 $[i,j]$ 中包含位置 $k$ 的奶牛的最大体重
   • f[k+1][j]：区间 $[k+1, j]$ 的最大和

为什么这样转移是正确的？

当选择一头喜欢区间 $[l', r']$ 且包含位置 $k$ 的奶牛时：

• 该奶牛会清空区间 $[l', r']$
• 剩余部分被分割成 $[i, k-1]$ 和 $[k+1, j]$ 两个独立区间
• 这两个区间可以独立计算最大值

样例解析

对于样例：

2 2
100 1 2  # 奶牛1：体重100，喜欢[1,2]
100 1 1  # 奶牛2：体重100，喜欢[1,1]

计算过程：

• g[1][1][1] = 100 (奶牛2)
• g[1][1][2] = 100 (奶牛1或2)
• g[2][1][2] = 100 (奶牛1)

DP计算：

• f[1][1] = 100
• f[2][2] = 0 (没有奶牛只喜欢派2)
• f[1][2] = max(f[2][2]+g[1][1][2]+0, f[1][1]+g[2][1][2]+0) = max(100, 100+100) = 200

复杂度分析

• 时间复杂度：$O(N^3)$
  • 预处理：$O(N^3)$
  • DP过程：$O(N^3)$
• 空间复杂度：$O(N^3)$

由于 $N \leq 300$，$300^3 = 27,000,000$ 在可接受范围内。

关键技巧

1. 三维预处理：记录每个位置在每个区间内的最大值
2. 区间DP框架：经典的区间动态规划结构
3. 分割点枚举：通过枚举分割点来处理区间划分

总结

这道题的解题亮点：

1. 问题转化：将奶牛吃派问题转化为区间选择问题
2. 预处理优化：通过三维数组预处理区间信息
3. 区间DP应用：使用标准的区间DP框架解决问题
4. 独立子问题：利用区间分割后的独立性简化问题

算法通过巧妙的预处理和动态规划，在 $O(N^3)$ 时间内解决了这个看似复杂的调度问题，展示了区间DP在解决区间选择问题中的强大能力。