自动搬运

查看原文

来自洛谷，原作者为

	wylt **

搬运于2025-08-24 22:14:58，当前版本为作者最后更新于2020-02-20 14:54:50，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

USACO 2019 December 铂金组T1 Greedy Pie Eaters

原题面（英文）：http://www.usaco.org/index.php?page=viewproblem2&cpid=972

官方题解（英文）：http://www.usaco.org/current/data/sol_pieaters_platinum_dec19.html

---

题意简述

有 M 头牛，N 个派，每头牛都有体重和吃派的范围，分别用 $w$, $l$, $r$ 表示，

每头牛按顺序轮流吃派，且牛 i 会吃掉此时 $\left[l_{i}\ ,r_{i}\right]$ 的所有派。

我们需要求出每头牛按顺序吃完后，满足所有牛都至少吃到一个的 $\max\sum\limits_{i=c1}^{ck}w_i$ 。

其中 $N\le300,\ w_{i}\le10^6$ 。

题目分析

容易看出本题是一道区间求极值的问题，而区间 dp 就刚好可以解决此类问题，再看数据范围 $N\le300$, 所以我们可以朝区间 dp 这方面思考一下。

那么我们可以得到一个基本思路， $f(i,j)=\max(\ f(i,j),\ f(i,k-1)+f(k+1,j)+p(k,i,j)\ )$ 。

其中 $i,j,k$ 为下标，表示第 $i$ 个派 ；

$f(i,j)$ 表示此时 $\left[i\ ,j\right]$ 已被吃完的最大 $\sum\limits_{}^{}w$ ；

$p(k,i,j)$ 表示当 k 还未被吃时能吃掉 k 且 $i\le l\le k\le r\le j$ 的最大的一个 $w$ ；

所以转移方程可以理解为通过合并 $f(i,k-1)+f(k+1,j)$ 更新 $f(i,j)$ 的值，

而第一个问题就来了：为什么是 $f(i,k-1)+f(k+1,j)$ 而不是 $f(i,k)+f(k+1,j)$ 呢？

因为题目要求每头牛都至少吃到一个，所以在合并时就必须满足 k 还未被吃，

而 $f(i,k)+f(k+1,j)$ 就可能存在两部分都已经被吃完的尴尬情况。

第二个问题，为什么 $p(k,i,j)$ 中 $i\le l\le k\le r\le j$ 呢？

因为现在我们要求合并时拥有最大 $w$ 的一个能吃掉第 k 个派的牛，

所以 k 必须在这头牛的 $l,r$ 之间，且不能把 $\left[i\ ,j\right]$ 以外的派吃掉，而影响了后面的更新

第三个问题，也是最难的一个问题，就是如何求出 $p(k,i,j)$。

我们知道， $p(k,i,j)$ 肯定是可以先预处理出来的，其实思路也基本就是区间 dp 的思路，

即 $p(k,i-1,j)=\max(\ p(k,i-1,j),\ p(k,i,j)\ )$ ；

$p(k,i,j+1)=\max(\ p(k,i,j+1),\ p(k,i,j)\ )$。

也就是通过已经得出的一个个向外更新，最终扩展到整个序列。

温馨提示（血的教训）：

我们可以发现下面代码的两个更新循环有许多不一样，但改变任何一个的顺序都会 wa 掉。

对于区间 dp 千万要注意循环的顺序，一般循环有三层，分为枚举 $i,j$ 和他们的合并点 $k$ ，

有两种顺序为 $i->j->k$ 和 $k->i->j$ ，

也就是 $k$ 的出现顺序不同，我们可以根据模拟的方法推出哪种顺序不对，

只要发现会用到未更新过的点更新自己就是错误的，一般很快就可以判断出来。

其次还要注意是从 $1$ 枚举到 $N$ 还是要反过来从 $N$ 枚举到 $1$ ，方法和上面一样，就不多说了。

---

代码

代码和官方题解的思路基本一样，但可读性可能会好一点。

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int f[305][305];
int p[305][305][305];

int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=m;i++){
		int w,l,r;
		cin>>w>>l>>r;
		for(int j=l;j<=r;j++){
			p[j][l][r]=w;//由于没有两头奶牛喜欢吃相同范围的派，可以不用比较大小，直接赋值即可 
		}
	}
	for(int k=1;k<=n;k++){
		for(int i=k;i>=1;i--){
			for(int j=k;j<=n;j++){
				//if为了防止下标超过[1,n] 
				if(i!=1){ 
					p[k][i-1][j]=max(p[k][i][j],p[k][i-1][j]);
				}
				if(j!=n){
					p[k][i][j+1]=max(p[k][i][j],p[k][i][j+1]);
				}
			}
		}
	}
	for(int i=n;i>=1;i--){
		for(int j=i;j<=n;j++){
			for(int k=i;k<j;k++){//k!=j是因为底下的f(k+1,j) 
				f[i][j]=max(f[i][j],f[i][k]+f[k+1][j]);//先把f(i,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)+p[k][i][j]);
				//同样要防止出现f(i,j)中，i>j的情况 
			}
		}
	}
	cout<<f[1][n];
	return 0;
}