几乎是对照着第三篇题解改了，依然不知道为什么总是错第5,6,8,9个点。答案似乎总是大的出奇：比如我第8个点输出的是9223091508069726873。求大佬帮忙看看。

#include<bits/stdc++.h>
#define ll long long
#define ri register int
using namespace std;
const int N=55,M=4010;
ll f[N][N][M],ans[N],li[M],a[M],b[M],c[M],g[N][N],best[N][N][M],last[N][N][M],tot;
void dfs(int l,int r,int k){
	if(l>r) return ;
	ans[last[l][r][k]]=li[best[l][r][k]];
	dfs(l,last[l][r][k]-1,best[l][r][k]);
	dfs(last[l][r][k]+1,r,best[l][r][k]);
}
int main(){
	int i,j,k,l,n,m;
	scanf("%d%d",&n,&m);
	for(i=1;i<=m;i++){
		scanf("%lld%lld%lld",&a[i],&b[i],&c[i]);
		li[i]=c[i];
	}
	sort(li+1,li+1+m);
	tot=unique(li+1,li+1+m)-li-1;
	for(i=1;i<=m;i++) c[i]=lower_bound(li+1,li+1+tot,c[i])-li;
	for(int len=1;len<=n;len++){
		for(i=1;i+len-1<=n;i++){
			j=i+len-1;
			memset(g,0,sizeof(g));
			for(k=1;k<=m;k++)
				if(i<=a[k]&&b[k]<=j)
					for(l=a[k];l<=b[k];l++)
						g[l][c[k]]++;
			for(l=i;l<=j;l++)
				for(k=tot;k>=0;k--)
					g[l][k]+=g[l][k+1];
			best[i][j][tot+1]=tot;
			last[i][j][tot+1]=i;
			for(k=tot;k>=1;k--){
				f[i][j][k]=f[i][j][k+1];
				best[i][j][k]=best[i][j][k+1];
				last[i][j][k]=last[i][j][k+1];
				for(l=i;l<=j;l++){
					if(f[i][j][k]<f[i][l-1][k]+f[l+1][j][k]+g[l][k]*li[k]){
						f[i][j][k]=f[i][l-1][k]+f[l+1][j][k]+g[l][k]*li[k];
						best[i][j][k]=k;
						last[i][j][k]=l;
					}
				}
			}
		}
	}
	dfs(1,n,1);
	printf("%lld\n",f[1][n][1]);
	for(i=1;i<=n;i++) printf("%lld ",ans[i]);
	return 0;
}