题目大意：

有 $M$ 头牛， $N$ 个派，每头牛会吃掉 $[l_i,r_i]$ 中的派，且有一个体重 $w_i$ 。要求选出一个顺序，使得当轮到一头牛时， 至少会吃 $1$ 个派，求 $\max\sum\limits_{}^{}w_i$ 。

$N \le 300 , w_i \le 10^6$ 。

思路：

区间dp。

设 $f(i,j)$ 表示第 $i$ 至 $j$ 个派被吃完，最大的 $\sum\limits_{}^{}w_i$ ，从 $f(i,k)$ 和 $f(k+1,j)$ 转移。

如果其中的牛吃了 $[i,j]$ 之外的派，那么有可能答案过大，因为有些派被算了两次。

所以规定奶牛吃派的范围 $l_x \ge i$ 且 $r_x \le j$ 。

基于贪心策略，可以假设新加入的那头牛只得到1个派，那么可以枚举剩下的派 $k$ ，得：

$f(i,j)=\max\{f(i,k)+f(k+2,j)+w_x\}，(l_x \ge i，r_x \le j)$ 。

由于枚举 $i,j,k$ 就有 $O(n^3)$ 了，那么 $w_x$ 必须预处理才行。

设 $g(i,j,k)$ 表示 $[i,j]$ 内，包含 $k$ 的奶牛的最大的 $w_i$ 。

$g(i,j,k)=\max\{g(i+1,j,k),g(i,j-1,k)\}$ 。

对于每单独一头奶牛进行初始化即可。

$f(i,j)=\max\{f(i,k+f(k+2,j)+g(i,j,k)\}$ 。

代码：

#include <iostream>
#include <cstdio>
#include <algorithm>
#include <cstring>

#define LL long long

using namespace std;

const int kM=1e5+5;
const int kN=305;

struct Node{
	int w,l,r;
}a[kM];

int n,m;
int g[kN][kN][kN];
LL f[kN][kN];

void Init(){
	scanf("%d%d",&n,&m);
	for(int i=1;i<=m;++i){
		scanf("%d%d%d",&a[i].w,&a[i].l,&a[i].r);
	}
}

int main(){
	Init();
	for(int i=1;i<=m;++i){
		int l=a[i].l,r=a[i].r;
		for(int j=l;j<=r;++j){
			g[l][r][j]=max(g[l][r][j],a[i].w);//对每头奶牛进行初始化
		}
	}
	for(int i=1;i<n;++i){
		for(int j=1;j+i<=n;++j){
			int k=i+j;
			for(int l=j;l<=k;++l){
				g[j][k][l]=max(g[j][k][l],max(g[j+1][k][l],g[j][k-1][l]));//预处理g数组
			}
		}
	}
	for(int i=0;i<n;++i){
		for(int j=1;j+i<=n;++j){
			int k=i+j;
			for(int l=j;l<=k;++l){
				f[j][k]=max(f[j][k],f[j][l-1]+f[l+1][k]+(LL)g[j][k][l]);
			}
		}
	}
	printf("%lld",f[1][n]);
	return 0;
}