题目传送门：P5851 [USACO19DEC] Greedy Pie Eaters P - 洛谷 | 计算机科学教育新生态 (luogu.com.cn)
这题第一眼一头雾水，就从它求最值的方向开始想，不是dp就是贪心，想了一会儿，这道题没法用贪心，因为我们无论是按牛的体重贪心还是按吃派个数贪心都是行不通的，那么真相只有一个，这是一道dp题，我们可以用dp[i][j]表示从i到j都被吃完时牛体重的最大值，那么在更大的一个范围l，r内，我们枚举一个断点k，此时可得dp[l][r] = max(dp[l][r]，dp[l][k-1]+p[k][i][j]+dp[k+1][r])，其中p(k,i,j) 表示当 k 还未被吃时能吃掉 k 且 i≤l≤k≤r≤j 的最大的一个w ，那么从断点，左右端点这些标志可以看出来这是区间dp了，引（
好了这个题到这里基本上就解决了，代码：
#include<bits/stdc++.h> using namespace std; const int N = 305; int n,m; int dp[N][N],sum[N][N][N]; int main(){ scanf("%d%d",&n,&m); for(int i = 1;i <= m;i++){ int w,l,r; scanf("%d%d%d",&w,&l,&r); for(int j = l;j <= r;j++){ sum[j][l][r] = w;//l到r之间的每个j都要附上初始值w } } for(int k = 1;k <= n;k++){ for(int i = k;i >= 1;i--){ for(int j = k;j < n;j++){//注意特判不要越界 if(i!=1) sum[k][i-1][j] = max(sum[k][i][j],sum[k][i-1][j]); if(j!=n) sum[k][i][j+1] = max(sum[k][i][j],sum[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++){//一样，特判不要越界 dp[i][j] = max(dp[i][j],(k!=i?dp[i][k-1]:0)+(k!=j?dp[k+1][j]:0)+sum[k][i][j]); } } } printf("%d",dp[1][n]); return 0; }