洛谷P5851 [USACO19DEC]Greedy Pie Eaters P 题解

题目链接：P5851 [USACO19DEC]Greedy Pie Eaters P

题意：

Farmer John 有 $M$ 头奶牛，为了方便，编号为 $1,\dots,M$。这些奶牛平时都吃青草，但是喜欢偶尔换换口味。Farmer John 一天烤了 $N$ 个派请奶牛吃，这 $N$ 个派编号为 $1,\dots,N$。第 $i$ 头奶牛喜欢吃编号在 $\left[ l_i,r_i \right]$ 中的派（包括两端），并且没有两头奶牛喜欢吃相同范围的派。第 $i$ 头奶牛有一个体重 $w_i$，这是一个在 $\left[ 1,10^6 \right]$ 中的正整数。

Farmer John 可以选择一个奶牛序列 $c_1,c_2,\dots,c_K$，并让这些奶牛按这个顺序轮流吃派。不幸的是，这些奶牛不知道分享！当奶牛 吃派时，她会把她喜欢吃的派都吃掉——也就是说，她会吃掉编号在 $[l_{c_i},r_{c_i}]$ 中所有剩余的派。Farmer John 想要避免当轮到一头奶牛吃派时，她所有喜欢的派在之前都被吃掉了这样尴尬的情况。因此，他想让你计算，要使奶牛按 $c_1,c_2,\dots,c_K$ 的顺序吃派，轮到这头奶牛时她喜欢的派至少剩余一个的情况下，这些奶牛的最大可能体重（$w_{c_1}+w_{c_2}+\ldots+w_{c_K}$）是多少。

显然是一个区间dp

设 $f[i][j]$ 表示吃完 $[i,j]$ 能获得的最大 $\sum w$

设 $g[k][i][j]$ 表示 $k$ 还没吃，准备吃掉 $k$ 时 $(i \le l_d \le k \le r_d \le j)$ 的最大 $w$

首先不尝试增加奶牛 $d$ ，即不考虑吃 $k$ ，有

$$f[i][j]=\max(f[i][j],f[i][k]+f[k+1][j])$$

考虑吃 $k$ ，尝试增加奶牛 $d$ ，有

$$f[i][j]=\max(f[i][j],f[i][k-1]+f[k+1][j]+g[k][i][j])$$

• 关于 $g[k][i][j]$ 如何限制 $(l_d \le k \le r_d)$

  考虑读入时处理每头奶牛 $g[t][l][r]=w,l \le t \le r$

• 如何更新 $g[k][i][j]$

  显然当 $[i,j]=[l_d,r_d]$ 时，已经在读入时更新了

  当 $i \le l_d$ 或 $j \ge r_d$ 时，我们可以通过

  $$g[k][i-1][j]=\max(g[k][i-1][j],g[k][i][j]) \\g[k][i][j+1]=\max(g[k][i][j+1],g[k][i][j])$$

  进行更新

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

代码：

#include <bits/stdc++.h>
using namespace std;
// #define int long long
// #define INF 0x3f3f3f3f3f3f3f3f
#define N (int)(305)
#define M (int)(5e4+15)
int n,m;
int f[N][N],g[N][N][N];
signed main()
{
    ios::sync_with_stdio(0);
    cin.tie(0);cout.tie(0);
    // freopen("check.in","r",stdin);
    // freopen("check.out","w",stdout);
    cin >> n >> m;
    for(int i=1,w,l,r; i<=m; i++)
    {
        cin >> w >> l >> r;
        for(int j=l; j<=r; j++)
            g[j][l][r]=w;
    }
    for(int len=1; len<=n; len++)
        for(int i=1,j=i+len-1; j<=n; i++,j++)
            for(int k=i; k<=j; k++)
            {
                if(i!=1)g[k][i-1][j]=max(g[k][i-1][j],g[k][i][j]);
                if(j!=n)g[k][i][j+1]=max(g[k][i][j+1],g[k][i][j]);
            }
    for(int len=1; len<=n; len++)
        for(int i=1,j=i+len-1; j<=n; i++,j++)
        {
            for(int k=i; k<j; k++)
                f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);
            for(int k=i; k<=j; k++)
                f[i][j]=max(f[i][j],(k!=i?f[i][k-1]:0)+(k!=j?f[k+1][j]:0)+g[k][i][j]);
        }
    cout << f[1][n];
    return 0;
}