Description：

有一行 $n$ 个位置，有 $m$ 个人，如果第 $l[i]$ 到 $r[i]$ 之间的最小值小于等于 $c[i]$ 的话第 $i$ 个人就会付出对应最小值的代价，给每个位置确定一个值使得所有人付出的总代价最大。

$1\leqslant n\leqslant 50,1\leqslant m\leqslant 4000$

Solution：

数据范围中 $n$ 很小， $m$ 也不大，可以考虑略微暴力的做法，设 $f[i][j][k]$ 表示在区间 $[i,j]$ ，区间最小值为 $k$ （离散化过，因为每个位置一定顶着某一个上限）付出的最大的代价，转移时就枚举 $p$ 作为最小值的位置，转移方程为： $$ f[i][j][k]=\min(f[i][p-1][k_1]+f[p+1][j][k_2]+cnt\times c[k]) $$ $cnt$ 代表整个区间落在 $[i,j]$ 中，跨过 $p$ 且 $k\leqslant c[w]$ 的人的个数，这个可以倒序枚举 $k$ 同时用双指针计算，转移方程的另一个限制是 $k_1,k_2\geqslant k$ ，这个可以维护一个后缀最大值，输出方案的话记一下每个状态从哪里转移来的就行了。

Code：

#include<algorithm>

#include<iostream>

#include<cstdlib>

#include<cstdio>

#include<cmath>

#include<cctype>

#include<cstring>

using namespace std;

#define R register

inline int rd()

{

	R int res = 0,f = 1;

	R char c = getchar();

	while(!isdigit(c))

	{

		if(c == '-')f = -1;

		c = getchar();

	}

	while(isdigit(c))

	{

		res = (res << 1) + (res << 3) + c - '0';

		c = getchar();

	}

	return res * f;

}

int n,m;

#define MAXN 60

#define MAXM 4010

struct seg

{

	int l,r,c;

}s[MAXM];

int b[MAXM],tot;

inline int v(int x){return lower_bound(b + 1,b + 1 + tot,x) - b;}

typedef long long ll;

ll f[MAXN][MAXN][MAXM];

ll g[MAXN][MAXN][MAXM];

int fr[MAXN][MAXN][MAXM];

int gr[MAXN][MAXN][MAXM];

bool cmp_c(seg a,seg b){return a.c > b.c;}

void pt(int fpos,int l,int r)

{

	if(l > r)return;

	if(l == r)

	{

		printf("%d ",b[fpos]);

		return;

	}

	pt(gr[l][fr[l][r][fpos] - 1][fpos],l,fr[l][r][fpos] - 1);

	printf("%d ",b[fpos]);

	pt(gr[fr[l][r][fpos] + 1][r][fpos],fr[l][r][fpos] + 1,r);

	return;

}

int main()

{

	scanf("%d%d",&n,&m);

	for(R int i = 1;i <= m;++i)

	{

		s[i].l = rd();s[i].r = rd();s[i].c = rd();

		b[i] = s[i].c;

	}

	sort(b + 1,b + 1 + m);

	tot = unique(b + 1,b + 1 + m) - b - 1;

	sort(s + 1,s + 1 + m,cmp_c);

	for(R int l = 1;l <= n;++l)

	{

		for(R int i = 1;i <= n - l + 1;++i)

		{

			R int j = i + l - 1;

			for(R int p = i;p <= j;++p)

			{

				R int sum = 0;

				for(R int k = tot,w = 1;k >= 1;--k)

				{

					while(w <= m && v(s[w].c) >= k)

					{

						if(i <= s[w].l && s[w].l <= p && p <= s[w].r && s[w].r <= j)++sum;

						++w;

					}

					if(g[i][p - 1][k] + g[p + 1][j][k] + sum * b[k] >= f[i][j][k])

					{

						f[i][j][k] = g[i][p - 1][k] + g[p + 1][j][k] + 1ll * sum * b[k];

						fr[i][j][k] = p;

					}

				}

			}

			for(R int k = tot;k >= 1;--k)

			{

				if(f[i][j][k] >= g[i][j][k + 1])

				{

					g[i][j][k] = f[i][j][k];

					gr[i][j][k] = k;

				}

				else

				{

					g[i][j][k] = g[i][j][k + 1];

					gr[i][j][k] = gr[i][j][k + 1];

				}

			}

		}

	}

	printf("%lld\n",g[1][n][1]);

	pt(gr[1][n][1],1,n);

	puts("");

	return 0;

}