洛谷 P3592 [POI2015]MYJ

题意

给定\(m\)个区间\([a_i,b_i]\)以及\(c_i\)，对于一个含有\(n\)个元素的序列\(ans[]\)，区间\(i\)对其的贡献为\(\min\{ans_i\}(i\in[a_i,b_i])<=c_i\ ?\ \min\{ans_i\}(i\in[a_i,b_i])\ :\ 0\)，要求构造一个序列\(ans[]\)，最大化区间的贡献之和。

\(n\leq50,m\leq4000\)

思路

打死都不可能想到状态设计DP系列

稍作分析半天就会发现：存在一组答案使得每个\(ans_i\)都是某个\(c_i\)。因为把某个答案替换成第一个大于等于它的\(c_i\)不会更劣，因此\(c_i\)的值并不影响做题，但是大小顺序是有用的所以我们将\(c_i\)离散化。

因为一个区间的代价之和只与最小值有关，而且数据范围的\(n\)也不大，所以考虑区间\(\texttt{DP}\)：

设\(f[l][r][k]\)表示区间\([l,r]\)内\(ans[]\)的最小值等于\(k\)的最大收益，\(g[p][j]\)为当前区间穿过\(p\)，且\(c\geq j\)的区间数量

枚举最小的位置\(p\)，那么包含\(p\)的区间的答案全都是\(k\)，之后转移

\[f[l][r][k]=\max(\max(f[l][p - 1][k] + f[p + 1][r][k]+g[p][k]*k,p\in[l,r]),f[l][r][k+1])
\]

\(\texttt{DP}\)时顺便记录记录决策点，然后\(dfs\)输出

时间复杂度\(O(n^3m)\)

代码

/*

Author:Loceaner

区间DP

*/

#include <cmath>

#include <cstdio>

#include <cstring>

#include <iostream>

#include <algorithm>

using namespace std;

const int A = 51;

const int B = 4011;

const int mod = 1e9 + 7;

const int inf = 0x3f3f3f3f;

inline int read() {

  char c = getchar(); int x = 0, f = 1;

  for ( ; !isdigit(c); c = getchar()) if (c == '-') f = -1;

  for ( ; isdigit(c); c = getchar()) x = x * 10 + (c ^ 48);

  return x * f;

}

struct node { int l, r, c; } a[B];

int n, m, tot, ans[B], res[B];

int pre[A][A][B], f[A][A][B], pos[A][A][B], g[A][B];

inline void work(int l, int r, int now) {

  if (l > r) return;

  int qwq = pos[l][r][now = pre[l][r][now]];

  ans[qwq] = res[now];

  work(l, qwq - 1, now), work(qwq + 1, r, now);

}

inline void update(int l, int r) {

  for (int i = l; i <= r; i++)

    for (int minn = 0; minn <= tot; minn++) g[i][minn] = 0;

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

    if (l <= a[i].l && a[i].r <= r)

      for (int j = a[i].l; j <= a[i].r; j++) g[j][a[i].c]++;

  for (int i = l; i <= r; i++)

    for (int j = tot - 1; j >= 1; j--) g[i][j] += g[i][j + 1];

}

inline void dp(int l, int r) {

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

    int maxn = 0;

    for (int p = l; p <= r; p++) {

      int now = f[l][p - 1][k] + f[p + 1][r][k] + g[p][k] * res[k];

      if (maxn <= now) maxn = now, pos[l][r][k] = p;

    }

    if (maxn >= f[l][r][k + 1]) f[l][r][k] = maxn, pre[l][r][k] = k;

    else f[l][r][k] = f[l][r][k + 1], pre[l][r][k] = pre[l][r][k + 1];

  }

}

signed main() {

  n = read(), m = read();

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

    a[i].l = read(), a[i].r = read(), a[i].c = read(), res[i] = a[i].c;

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

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

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

    a[i].c = lower_bound(res + 1, res + tot + 1, a[i].c) - res;

  for (int i = n; i >= 1; i--)

    for (int j = i; j <= n; j++)

      update(i, j), dp(i, j);

  work(1, n, 1);

  cout << f[1][n][1] << '\n';

  for (int i = 1; i <= n; i++) cout << ans[i] << " ";

  return 0;

}