P3592 [POI2015]MYJ

POI 合集。

区间 DP 好题。因为 $c_i$ 具体值不重要，只关心相对大小，所以离散化 $c_i$。设 $f_{l,r,x}$ 表示区间 $[l,r]$ 最小值不小于为 $x$ 的答案。由于要输出方案所以记录 $v_{l,r,x}$ 表示 $f_{l,r,x}$ 的区间最小值取了 $v_{l,r,x}$，以及 $d_{l,r,x}$ 表示 $f_{l,r,x}$ 的分割点，这说明 $f_{l,r,x}$ 由 $f_{l,d_{l,r,x}-1,v_{l,r,x}}$ 和 $f_{d_{l,r,x}+1,r,v_{l,r,x}}$ 转移而来。

转移枚举断点 $k$，则贡献为 $f_{l,r,x}=cx+\max_{k\in [l,r]}f_{l,k-1,x}+f_{k+1,r,x}$，其中 $c$ 是满足 $l\leq a_i\leq k\leq b_i \leq r$ 的 $i$ 的个数，可以在枚举 $l,r,k$ 的时候 $\mathcal{O}(m)$ 预处理。注意还要和 $f_{l,r,x+1}$ 取 $\max$。时间复杂度 $\mathcal{O}(n^3m)$。

const int N = 50 + 5;
const int M = 4e3 + 5;

int n, m, a[M], b[M], c[M], d[M];
int ans[N], f[N][N][M], buc[N][N];
pii tr[N][N][M];
void dfs(int l, int r, int p) {
	if(l > r) return;
	pii it = tr[l][r][p];
	ans[it.se] = d[it.fi];
	dfs(l, it.se - 1, it.fi), dfs(it.se + 1, r, it.fi);
}
bool Med;
int main(){
	cin >> n >> m;
	for(int i = 1; i <= m; i++) cin >> a[i] >> b[i] >> c[i], d[i] = c[i];
	sort(d + 1, d + m + 1);
	for(int i = 1; i <= m; i++) c[i] = lower_bound(d + 1, d + m + 1, c[i]) - d;
	for(int i = m; i; i--) {
		for(int j = 1; j <= m; j++) if(c[j] == i)
			for(int l = 1; l <= a[j]; l++) for(int r = b[j]; r <= n; r++) buc[l][r]++;
		for(int len = 1; len <= n; len++)
			for(int l = 1, r = len; r <= n; l++, r++) {
				f[l][r][i] = f[l][r][i + 1], tr[l][r][i] = tr[l][r][i + 1];
				for(int p = l; p <= r; p++) {
					int coef = buc[l][r] - buc[l][p - 1] - buc[p + 1][r];
					int v = f[l][p - 1][i] + f[p + 1][r][i] + coef * d[i];
					if(v > f[l][r][i]) f[l][r][i] = v, tr[l][r][i] = {i, p};
				} if(tr[l][r][i].fi == 0) tr[l][r][i] = {i, l};
			}
	} cout << f[1][n][1] << endl, dfs(1, n, 1);
	for(int i = 1; i <= n; i++) cout << ans[i] << " ";
	return 0;
}