洛谷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;
}