• MYJ 是我们的红太阳，让我们一起赞美 MYJ 吧。

题意

• 题面。
• 有 $m$ 个对于长度为 $n$ 的序列 $a$ 的估价函数 $f_i=[\min_{k=l_i}^{r_i}a_k\le c_i]\cdot \min_{k=l_i}^{r_i}a_k$。
• 构造方案，最大化：

• $n\le 50,m\le 4000,c_i\le 5\times 10^5$。

分析

• 不愧是 MYJ 大奆佬的题目，蒟蒻一看就不会了。
• MYJ 说，要简化问题：所以我们可以发现一个简单的信息，所有的 $a_i$ 应该都是 $c_i$ 中的一个，否则显然可以使得估价函数的值变大，所以 $5\times 10^5$ 变成了 $4000$。
• MYJ 说，要学会变换：所以我们假设 $f(l,r)$ 为使得 $l\le l_i,r_i\le r$ 的所有估价函数的和最大的安排，来思考它的最优子结构性质。
• 让我们任意选定一个 $g$ 作为 $[l,r]$ 的中点并强行让它为最小值，那么所有经过 $g$ 的区间就全部处理完毕了，问题被分为两个互相独立的区间。
• 所以我们设 $f(l,r,k)$ 为设定让 $a_l$ 到 $a_r$ 大于等于 $c_k$，处理完被 $[l,r]$ 区间覆盖的估价函数的最优方案。
• 聪明地转移，时间复杂度是 $O(n^3m)$，空间复杂度是 $O(n^2m)$，聪明地剪枝，复杂度绝对卡不满，对于输出方案的问题，我们显然可以在算出最优的答案后轻易地倒推。
• 所以我们就成功地水过了这道题：真是让人感到无尽地愉悦啊！比记忆化搜索可能会慢一点。

#include<bits/stdc++.h>
const int N=55,M=44000,INF=500000; 
using namespace std;
int n,m,t,a[N],c[M],f[N][N][M];
bool ok[N][N][M];
struct que
{
	int l,r,c;
	bool operator < (const que &b)
	{
		return c<b.c;
	}
}q[M];
vector<que>g[N][N];
int main()
{
	scanf("%d%d",&n,&m);
	for(int i=0;i<m;++i)
	{
		scanf("%d%d%d",&q[i].l,&q[i].r,&q[i].c);
		c[i]=q[i].c;
	}
	sort(c,c+m);
	t=unique(c,c+m)-c;
	for(int i=0;i<m;++i)
		q[i].c=lower_bound(c,c+t,q[i].c)-c;
	for(int i=1;i<=n;++i)
	{
		for(int j=0;j<m;++j)
			if(i<=q[j].l)g[i][n].push_back(q[j]);
		sort(g[i][n].begin(),g[i][n].end());
		for(int j=n-1;j>=i;--j)
			for(auto z:g[i][j+1])
				if(z.r<=j)g[i][j].push_back(z);	
	}
	for(int k=1;k<=n;++k)
		for(int l=1;l+k-1<=n;++l)
		{
			int r=l+k-1;
			for(int d=l;d<=r;++d)
			{
				int cnt=0;
				for(auto z:g[l][r])
					if(z.l<=d&&d<=z.r)++cnt;
				for(auto z:g[l][r])
					if(z.l<=d&&d<=z.r)
						f[l][r][z.c]=max(f[l][r][z.c],f[l][d-1][z.c]+f[d+1][r][z.c]+cnt--*c[z.c]);
			}
			for(int w=t-2;w>=0;--w)
				f[l][r][w]=max(f[l][r][w],f[l][r][w+1]);
		}
	printf("%d\n",f[1][n][0]);ok[1][n][0]=1;
	for(int k=n;k>=1;--k)
		for(int l=1;l+k-1<=n;++l)
		{
			int r=l+k-1,w=0;
			while(w<t&&!ok[l][r][w])++w;
			if(w==t&&t>0)continue;
			if(g[l][r].empty())
			{
				fill(a+l,a+r+1,INF);
				continue;
			}
			while(w+1<t&&f[l][r][w]==f[l][r][w+1])++w;
			for(int d=l;d<=r;++d)
			{
				int cnt=0;
				for(auto z:g[l][r])
					if(z.l<=d&&d<=z.r&&w<=z.c)++cnt;
				if(f[l][r][w]==f[l][d-1][w]+f[d+1][r][w]+cnt*c[w])
				{
					ok[l][d-1][w]=1,ok[d+1][r][w]=1,a[d]=c[w];
					break;
				}
			}
		}
	for(int i=1;i<=n;++i)printf("%d ",a[i]);
	return 0;
}

• 我觉得这种方法还是有启发性的吧，不愧是 MYJ 啊！