526互联

[USACO19DEC] Greedy Pie Eaters P 区间dp

发布时间 2023-10-19 16:08:24作者: HL_ZZP

题目背景

Farmer John has MM cows, conveniently labeled 1…M1…M, who enjoy the occasional change of pace from eating grass. As a treat for the cows, Farmer John has baked NN pies (1≤N≤3001≤N≤300), labeled 1…N1…N. Cow ii enjoys pies with labels in the range [li,ri][li​,ri​] (from lili​ to riri​ inclusive), and no two cows enjoy the exact same range of pies. Cow ii also has a weight, wiwi​, which is an integer in the range 1…1061…106.

Farmer John may choose a sequence of cows c1,c2,…,cK,c1​,c2​,…,cK​, after which the selected cows will take turns eating in that order. Unfortunately, the cows don't know how to share! When it is cow cici​'s turn to eat, she will consume all of the pies that she enjoys --- that is, all remaining pies in the interval [lci,rci][lci​​,rci​​]. Farmer John would like to avoid the awkward situation occurring when it is a cows turn to eat but all of the pies she enjoys have already been consumed. Therefore, he wants you to compute the largest possible total weight (wc1+wc2+…+wcKwc1​​+wc2​​+…+wcK​​) of a sequence c1,c2,…,cKc1​,c2​,…,cK​ for which each cow in the sequence eats at least one pie.

题目描述

Farmer John 有 MM 头奶牛，为了方便，编号为 1,…,M1,…,M。这些奶牛平时都吃青草，但是喜欢偶尔换换口味。Farmer John 一天烤了 NN 个派请奶牛吃，这 NN 个派编号为 1,…,N1,…,N。第 ii 头奶牛喜欢吃编号在 [li,ri][li​,ri​] 中的派（包括两端），并且没有两头奶牛喜欢吃相同范围的派。第 ii 头奶牛有一个体重 wiwi​，这是一个在 [1,106][1,106] 中的正整数。

Farmer John 可以选择一个奶牛序列 c1,c2,…,cKc1​,c2​,…,cK​，并让这些奶牛按这个顺序轮流吃派。不幸的是，这些奶牛不知道分享！当奶牛 吃派时，她会把她喜欢吃的派都吃掉——也就是说，她会吃掉编号在 [lci,rci][lci​​,rci​​] 中所有剩余的派。Farmer John 想要避免当轮到一头奶牛吃派时，她所有喜欢的派在之前都被吃掉了这样尴尬的情况。因此，他想让你计算，要使奶牛按 c1,c2,…,cKc1​,c2​,…,cK​ 的顺序吃派，轮到这头奶牛时她喜欢的派至少剩余一个的情况下，这些奶牛的最大可能体重（wc1+wc2+…+wcKwc1​​+wc2​​+…+wcK​​）是多少。

输入格式

第一行包含两个正整数 N,MN,M；

接下来 MM 行，每行三个正整数 wi,li,riwi​,li​,ri​。

输出格式

输出对于一个合法的序列，最大可能的体重值。

输入输出样例

输入 #1
2 2
100 1 2
100 1 1
输出 #1
200

说明/提示

样例解释

在这个样例中，如果奶牛 11 先吃，那么奶牛 22 就吃不到派了。然而，先让奶牛 22 吃，然后奶牛 11 只吃编号为 22 的派，仍可以满足条件。

对于全部数据，1≤N≤300,1≤M≤N(N−1)2,1≤li,ri≤N,1≤wi≤1061≤N≤300,1≤M≤2N(N−1)​,1≤li​,ri​≤N,1≤wi​≤106。

数据范围

对于测试点 2−52−5，满足 N≤50,M≤20N≤50,M≤20；

对于测试点 6−96−9，满足 N≤50N≤50。

USACO 2019 December 铂金组T1

一眼dp
但不是一道很基础的dp
有区间的影响，用线性dp后效性难以处理，明显是区间dp
但是，区间dp常用的枚举区间断点合并的操作缺不是那么适用
先用这种常规办法考虑看看
设f[i][j]表示，区间[i,j]上面的派都已经被占用时，满足的奶牛的最大体重和
但是，我们是可以空着不吃的，可能是因为没有符合要求的奶牛，也可能就是不需要
这种情况在转移的时候会导致复杂度增加，因为要么在枚举断点的时候考虑到这一点，要么就是在转移后将“空着”这种情况一同转移
似乎。。都是增加一个n

难点似乎是“顺序”
顺序。。怎么考虑？或者说是怎么排除？
“dp一般都是考虑上一步与最后一步的关系”

我所纠结的顺序，其实是因为其可能会干扰合并，现在所提的新方法就是可以解决这种问题的方法

其实，我们完全不需要担心其中的空位能够产生的价值，因为这种情况如果更优秀，那根据最优子结构，肯定会被转移过来
我担心的其实是这个最优子结构的不成立，也就是更加优秀的情况没有被转移
我们可以在进行加入新牛操作之前先做一遍普通的转移，将先前的状态先合并，这样即使是空的区间，也会有一个从之前的值得到的目前的最优解
这个是之前我没学过的新方法啊。。
学到了

然后就是怎么添加新的牛
首先，一头牛需要吃掉一个区间，但实际上只需要有一个派它就能转移
所以我们枚举一个区间断点，或者说是，枚举最后一只牛，吃掉的是哪一个派（即使是吃了一个区间，我们也不管，因为无所谓，我们状态设计考虑了这个情况，其实它就算把那个区间里的都吃了都没事）
也许不是枚举，而是找到一个满足要求的体重最大的牛，而k没有被吃，就说明了它还没有被考虑（居然这样考虑顺序！也许关系顺序就是题目的陷阱，我们关系的根本就不是顺序，而是有没有转移的条件）

所以转移方程就是
f[i][j]=max(f[i][j],f[i][k-1]+f[k+1][j]+g[i][j][k])
g[i][j][k]表示吃的区间在i，j之间，然后需要吃掉k的奶牛之中的体重最大的奶牛
这个也是一个基础的区间dp

看看有些什么能够总结

1.对于那些可能产生作用的空位，我们可以直接转移，那些能够放进去的情况，我们在后面会考虑，具体的体现就是，我们先进行一遍不增加新牛的转移，也就是普通的区间合并，在进行加牛的转移

2.“当我不好"拆分-合并"的时候，先考虑最后执行的操作，再用这个最后执行的操作把区间分成两部分，可以视作"合并-拆分"。”这个是在洛谷上看到的dalao的总结。
这也算是区间dp的一种很重要的套路，因为这个最后执行的操作，某种意义上是一种“顺序”

 

3.思考我们需要考虑的到底是什么，这个题目里面直接提到了顺序这个东西，这是一种误导，因为我们在意的其实不是顺序，而是能否放进去 这是完全不一样的。
或者可以说是我们通过考虑最后的操作来排除所谓“顺序要求”带来的影响。

代码

#include<bits/stdc++.h>
#define ll long long
using namespace std;
inline int read() {
    char c=getchar();int a=0,b=1;
    for(;c<'0'||c>'9';c=getchar())if(c=='-')b=-1;
    for(;c>='0'&&c<='9';c=getchar())a=a*10+c-48;return a*b;
}
int n,m,w[30001],l[30001],r[30001],g[301][301][301],f[301][301];
int main()
{
    n=read();m=read();
    for(int i=1;i<=m;i++)
    {
        w[i]=read();
        l[i]=read();
        r[i]=read();
//        f[l[i]][r[i]]=w[i];
        for(int j=l[i];j<=r[i];j++)
        {
            g[j][l[i]][r[i]]=w[i];
        }
    }
    for(int i=1;i<=n;i++)//Çø¼ä³¤¶È 
    {
        for(int j=1;i+j-1<=n;j++)//×ó¶Ëµã 
        {
            int r=i+j-1;
            for(int k=j;k<=r;k++)//¶Ïµã 
            {
                g[k][j][r] = max(g[k][j][r],max(g[k][j+1][r],g[k][j][r-1]));
            }
        }
    }
    for(int i=1;i<=n;i++){
        for(int j=1;i+j-1<=n;j++){
            int r=i+j-1;
            for(int k=j;k<r;k++){
                f[j][r]=max(f[j][r],f[j][k]+f[k+1][r]);
            }
            for(int k=j;k<=r;k++){
                f[j][r]=max(f[j][r],f[j][k-1]+f[k+1][r]+g[k][j][r]);
            }
        }
    }
    cout<<f[1][n]<<endl;
    return 0;
}