如果只考虑选哪些奶牛吃派和奶牛吃派的顺序，就会陷入僵局，那么我们可以考虑派的情况。
套路地令 (f_{i,j}) 表示 (isim j) 这一段派，能满足一些奶牛，它们的最大可能体重。
[f_{i,j}=f_{i,k-1}+f_{k+1,j}+w_p(ileq l_pleq kleq r_pleq j)
]
因为一头奶牛至少吃一个派，所以就可以枚举这个派是什么，要满足的条件是这头奶牛吃派不会影响到 (isim j) 范围之外的派且 (k) 位置的派能吃到。
直接搞显然是 (O(N^3M)) 的，仔细分析一下，发现奶牛是否合法仅仅取决于 (i,j,k) 对其 (l,r) 的限制，奶牛产生的贡献也仅仅取决于其本身的 (w)。不妨令 (g_{i,j,k}) 表示在该限制下最大的 (w)，那么转移方程就变为：
[f_{i,j}=f_{i,k-1}+f_{k+1,j}+g_{i,j,k}
]
接着就考虑 (g) 怎么搞。
初始化：(g_{l_p,r_p,l_psim r_p}=w_p)（每头奶牛吃派的范围不同）。
转移：(g_{i,j,k}=max{g_{i+1,j,k},g_{i,j-1,k}})。
其实就是预处理一下区间 (max)。
时间复杂度 (O(N^3))。
code:
#include<bits/stdc++.h>
using namespace std;
#define N 305
#define Max(x,y)((x)>(y)?x:y)
#define For(i,x,y)for(i=x;i<=(y);i++)
int g[N][N][N],f[N][N];
int main()
{
int n,m,i,j,w,l,r,len,k;
scanf("%d%d",&n,&m);
For(i,1,m)
{
scanf("%d%d%d",&w,&l,&r);
For(j,l,r)g[l][r][j]=w;
}
For(len,1,n-1)
For(i,1,n)
{
j=i+len-1;
if(j>n)break;
For(k,i,j)g[i][j+1][k]=Max(g[i][j+1][k],g[i][j][k]),g[i-1][j][k]=Max(g[i-1][j][k],g[i][j][k]);
}
For(len,1,n)
For(i,1,n)
{
j=i+len-1;
if(j>n)break;
For(k,i,j)f[i][j]=Max(f[i][j],f[i][k-1]+f[k+1][j]+g[i][j][k]);
}
printf("%d",f[1][n]);
return 0;
}