[USACO19DEC]Greedy Pie Eaters P

Posted on Edited on In Word count in article: 338 Reading time ≈ 1 mins.
None

[USACO19DEC]Greedy Pie Eaters P

题目大意

有\(n\)个派可以吃

有\(m\)头牛来吃

第\(m\)头牛的重量为\(w_i\)，这头牛要吃的区间为\([l_i,r_i]\)

然后你是要保证每头牛都有的吃

那么你可以安排这些牛吃派的顺序

最后会得到这样一个序列\(c_1,c_2\cdots c_n\)

求： \[ ans = max(\sum_{i=1}^nw_{c_i}) \]

分析

看上去像个贪心啥的

但是贪心不能保证每头牛都有得吃，所以我们考虑\(Dp\)

参考官方题解

可以，就是这个意思

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
#include <bits/stdc++.h>

using namespace std;

typedef long long ll;
const int maxn = 300 + 10;
const int mod = 1e9 + 7;

inline int __read()
{
    int x(0), t(1);
    char o (getchar());
    while (o < '0' || o > '9') {
        if (o == '-') t = -1;
        o = getchar();
    }
    for (; o >= '0' && o <= '9'; o = getchar()) {
        x = (x << 1) + (x << 3) + (o ^ 48);
    }
    return x * t;
}

int f[maxn][maxn][maxn];
int g[maxn][maxn];

signed main()
{
    int n = __read(), m = __read();
    while (m--) {
        int w = __read(), l = __read(), r = __read();
        for (int p = l; p <= r; ++p)
            f[p][l][r] = w;
    }

    for (int p = 1; p <= n; ++p)
        for (int l = p; l >= 1; --l)
            for (int r = p; r <= n; ++r)
                f[p][l - 1][r] = max(f[p][l - 1][r], f[p][l][r]),
                f[p][l][r + 1] = max(f[p][l][r + 1], f[p][l][r]);

    for (int r = 1; r <= n; ++r)
        for (int l = r; l; --l)
            for (int k = l; k <= r; ++k)
                g[l][r] = max(g[l][r], g[l][k - 1] + g[k + 1][r] + f[k][l][r]);
    
    printf ("%d\n", g[1][n]);
    system("pause");
}