Luogu P5851 [USACO19DEC]Greedy Pie Eaters P

题目描述

https://www.luogu.com.cn/problem/P5851

简要题意：现在有 $n$ 个派以及 $m$ 个奶牛，第 $i$ 个奶牛只吃 $[l_i,r_i]$ 的派，同时第 $i$ 个奶牛如果吃到派，则有 $w_i$ 的贡献，现在要求选择若干个奶牛，按照某种顺序排序后，保证每个奶牛都能吃到派，且它们的贡献和最大，当轮到一个奶牛吃派时，它会将 $[l,r]$ 内所有剩下的派都吃掉

$n\le 300,m\le \frac{n(n+1)}{2}$

Solution

我们令 $f[i][j]$ 表示只吃区间 $[i,j]$ 内的派的最大贡献，我们枚举最后一个吃派的奶牛和它位置 $k$，能够得到如下转移 $f[i][j]=max(f[i][k-1]+f[k+1][j]+g[k][i][j])$，$g[k][i][j]$ 表示包含 $k$ 且在 $[i,j]$ 内的贡献最大的奶牛，$g[k][i][j]$ 可以 $O(n^3)$ 预处理

总的时间复杂度 $O(n^3)$

#include <iostream>
#include <algorithm>
#define maxn 310
using namespace std;

int n, m;

int f[maxn][maxn], g[maxn][maxn][maxn];
int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr); cout.tie(nullptr);

    cin >> n >> m;
    for (int i = 1; i <= m; ++i) {
        int x, y, z; cin >> z >> x >> y;
        for (int j = x; j <= y; ++j) g[j][x][y] = z;
    }
    for (int len = 1; len <= n; ++len) 
        for (int i = 1, j = len; j <= n; ++i, ++j) 
            for (int k = i; k <= j; ++k) 
                g[k][i][j] = max({ g[k][i][j], g[k][i + 1][j], g[k][i][j - 1] });
    for (int len = 1; len <= n; ++len)
        for (int i = 1, j = len; j <= n; ++i, ++j) 
            for (int k = i; k <= j; ++k) 
                f[i][j] = max(f[i][j], f[i][k - 1] + f[k + 1][j] + g[k][i][j]);
    cout << f[1][n] << "\n";
    return 0;
}