#include<cstdio>
#include<algorithm>
using namespace std;
const int MAXN=55,MAXM=4e3+5;
int N,M,A[MAXM],B[MAXM],C[MAXM],D[MAXM],cnt;
int g[MAXN][MAXM],bkp[MAXN][MAXN][MAXM],dp[MAXN][MAXN][MAXM];
int apc[MAXN][MAXN][MAXM],sol[MAXN];
void discrete(){
	for(int i = 1;i <= M;i++)D[i]=C[i];
	sort(D+1,D+M+1);
	cnt=unique(D+1,D+M+1)-(D+1);
	for(int i = 1;i <= M;i++)C[i]=lower_bound(D+1,D+cnt+1,C[i])-D;
}

void get_final_solu(int l,int r,int p){
	if(l<0||r<0||l>r) return;
	p=apc[l][r][p];
	int pos=bkp[l][r][p];
	if(sol[pos])return;
	sol[pos]=D[p];
	get_final_solu(l,pos-1,p),get_final_solu(pos+1,r,p);
}
int main(){
	scanf("%d%d",&N,&M);
	for(int i = 1;i <= M;i++)scanf("%d%d%d",&A[i],&B[i],&C[i]);
	discrete();
	for(int i = N;i;i--){
		for(int j = i;j <= N;j++){
			for(int k = i;k <= j;k++)for(int l = 0;l <= cnt;l++)g[k][l]=0;
			for(int m = 1;m <= M;m++)if(i<=A[m]&&B[m]<=j){
				for(int k = A[m];k <= B[m];k++)g[k][C[m]]++;
			}
			for(int k = i;k <= j;k++)for(int l = cnt-1;l;l--)g[k][l]+=g[k][l+1];
			for(int l = cnt;l;l--){
				int maxw=0;
				for(int k = i;k <= j;k++){
					int w=dp[i][k-1][l]+dp[k+1][j][l]+g[k][l]*D[l];
					if(maxw<=w)maxw=w,bkp[i][j][l]=k;
				}
				if(maxw>=dp[i][j][l+1])dp[i][j][l]=maxw,apc[i][j][l]=l;
				else dp[i][j][l]=dp[i][j][l+1],apc[i][j][l]=apc[i][j][l+1];
			}
		}
	}
	printf("%d\n",dp[1][N][1]);
	get_final_solu(1,N,1);
	for(int i = 1;i <= N;i++)printf("%d ",sol[i]);
	return 0;
}

代码第四十行if(maxw>=dp[i][j][l+1]那里，为什么大于等于不能改成大于？
改了的话求方案的函数就会进死循环，但按道理来说=的时候说明两种转移方式均可啊。。。