题目描述

题解

还是一个很 naive 的 DP 方程：设 \(dp_i\) 表示到第 \(i\) 句的最小花费，\(sum_i\) 是前 \(i\) 句的总长度，得 \(dp_i = \min\limits_{j = 0}^{i - 1}\{dp_j + \mid sum_i - sum_j - 1 - L \mid^p\}\)

然后这个复杂度是 \(O(n^2)\) 的，只有 \(30\)（这个出题人一点都不良心）。

考虑怎么优化它。

特殊的，对于这一题，我们把 \(\mid sum_i - sum_j - 1 - L \mid\) 单独提出来，那么可以去掉绝对值，得到一个单增的函数，显然可以二分最小值来转移。

推广到一半情况，那应该是转移方程形如 \(dp_i = \min / \max \limits_{j = 1}^{i - 1} dp_j + f_{i, j}\)，记 \(i\) 是从 \(p_i\) 转移得来，有 \(p_i \le p_{i + 1}\)。

这个叫做决策单调性，换句话说就是后面的 \(dp\) 值由后面的转移而来，转移位置单调不降。

那有什么函数能满足决策单调性呢。

首先对于任意两个 \(dp\) 的转移不能有公共值。形式化的，用 \(g_i(j)\) 表示第 \(i\) 个元素由第 \(j\) 个转移而来的花费，\(\forall i, j\)，\(\mid\text{Intersection}(i, j)\mid\le 1\)，也就是只有至多一个交点。

严格的我也不会证明（捂脸

感性理解一下，如果有至少两个交点那么我们无法判断在当前区间内选择哪一个更优（虽然两个交点应该可以乱搞出转移区间的范围），但如果只有一个，我们就能确定在这个交点前选择哪一个在这个交点后选择哪一个。

然后引用 FlashHu 大佬的话： > 如果导函数递增、求最大值（柠檬），或者导函数递减、求最小值，要用单调栈； > > 如果导函数递增、求最小值（本题），或者导函数递减、求最大值（Lightning Conductor），要用单调队列。

回到这一题，刚才已经得出了转移具有单调性那么用队列维护可以转移的区间，然后每次转移二分位置。

#include <cstdio>
#include <cstring>
#include <cmath>

#define double long double

const int N = 1e5 + 10;

int n, l, p;

double FastPow(double a, int b) {
  double res = 1;
  for (; b; b >>= 1, a = a * a)
    if (b & 1)
      res = res * a;
  return res;
}

double dp[N];
int sum[N];

double Check(int i, int j) {
  return dp[j] + FastPow(abs(sum[i] - sum[j] - l - 1), p);
}

int BinarySearch(int ql, int qr) {
  int l = 0, r = n + 1, res;
  while (l <= r) {
    int mid = (l + r) >> 1;
    if (Check(mid, ql) < Check(mid, qr))
      l = mid + 1, res = mid + 1;
    else
      r = mid - 1;
  }
  return res;
}

char s[N][40];
int q[N];
int pos[N], pre[N];

int main() {
  int T;
  scanf("%d", &T);
  while (T--) {
    scanf("%d%d%d", &n, &l, &p);
    for (int i = 1; i <= n; ++i) {
      scanf("%s", s[i] + 1);
      sum[i] = sum[i - 1] + strlen(s[i] + 1) + 1;
    }
    int he = 1, ta = 1;
    q[he] = 0;
    for (int i = 1; i <= n; ++i) {
      while (he < ta && pos[he] <= i)
        ++he;
      dp[i] = Check(i, q[he]), pre[i] = q[he];
      while (he < ta && pos[ta - 1] >= BinarySearch(q[ta], i))
        --ta;
      pos[ta] = BinarySearch(q[ta], i);
      q[++ta] = i;
    }
    if (dp[n] > 1e18) {
      printf("Too hard to arrange\n");
    } else {
      printf("%.0Lf\n", dp[n]);
      int tp = 0;
      q[tp] = n;
      int i = n;
      for (; i; q[++tp] = i = pre[i])
        ;
      for (; tp; --tp) {
        for (i = q[tp] + 1; i < q[tp - 1]; ++i)
          printf("%s ", s[i] + 1);
        puts(s[i] + 1);
      }
    }
    puts("--------------------");
  }
  return 0;
}

hello_world2005's blog

「NOI2009」诗人小G 题解

题目描述

题解