「Solution」诗人小G题解

这题和斜率优化放一起就很离谱

$\mathcal{Link}$

link

$\mathcal{Sol}$

题目已经很清楚了，不难想到一个朴素的 dp。定义 $sum_i$ 为诗句长度的前缀和， $dp_i$ 为以 $i$ 结尾，已经排版好的诗歌的不和谐度。

则有
$$ dp_i = \min\{ dp_j + | sum_i - sum_j + i - j - 1 - l | ^ p \mid 0 \le j < i \} $$
这样是一个 $\mathcal{O(n^2)}$ 的时间复杂度。

打满有 30pts 。

---

看到 $n \le 1e5$ ，意味着 $\mathcal{O(n)}$ 或 $\mathcal{O(n \log n)}$ 这样的时间复杂度比较正确。

其实分析数据范围都能猜到这道题的决策大概率是有单调性的。

结论是这道题确实有决策单调性的性质。

$\mathcal{Pro}$

对于两个决策点 $i k$ 时 $j$ 优于 $i$ ，当决策点 $k' < k$ 时 $i$ 优于 $j$ 。

我们定义以 $k$ 为决策点的函数为 $g_k$ 。

那么 $g_k(i) = dp_k + \mid sum_i - sum_k + i - k - 1 - l\mid ^ p$ 。

可以看到 $g_k(i)$ 以 $sum_k + k + 1 + l$ 为对称轴，且 $p$ 是定值，$sum_i + i$ 单调递增。

如果你把中间的 $sum_i + i$ 视作连续的，或者干脆把 $sum_i + i$ 换成 $i$ ，那么这一堆函数是可以通过平移转化的。

在满足函数间能平移转换后，就可以保证两两之间只有一个交点。

$\mathcal{Code}$

重点在如何套路化地写这种决策单调性的题。

那么把每个点作为决策点可以找的属于它的决策区间。

可以用一个结构体保存决策区间的信息。

struct Node {
    int l, r, pos;
} q[MAXN];

首先初始化，塞一个决策点 0 ，决策区间是 [1, n] 。

head = 1, tail = 0, q[++tail] = Node{1, n, 0};

对于每个当前点，首先计算当前的 dp[i] 值。

这时检查队头，如果队首元素的决策区间的右端点够不到当前点（就是说当前点不会队首元素更新）， q[tail].r < i ，那么就弹掉它。等拿到可行的队首后，用队首元素计算 dp[i] 。

考虑加入当前的决策点 i 。

从后往前考虑，如果当前决策点对队尾元素的左区间比队尾元素的决策点对队尾元素的左区间更优，直接弹掉队尾。换句话说，当前决策点的 “管辖范围” 比队尾的更广，能更快地把队尾更前面的决策点顶掉。

while (head < tail && cal(q[tail].l, i) <= cal(q[tail].l, q[tail].pos)) tail--;

在不断弹出队尾后，会发现一个情况，当前决策点管不到队尾的左端点，但是对于队尾的右端点来说，当前的决策点会更优。也就是队尾的 “管辖范围” 需要割开。

因为已知单调性，所以可以对 [q[tail].l, q[tail].r] 这段区间进行二分，找到划分点，最后加入当前的决策点的决策区间即可。

int l = q[tail].l, r = q[tail].r;
while (l < r) {
    int mid = (l + r + 1) >> 1;
    if (cal(mid, q[tail].pos) > cal(mid, i)) r = mid - 1;
    else l = mid;
}
if (l > q[tail].l) q[tail].r = l;
else tail--;

q[++tail] = Node{l, n, i};

给个完整代码

#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define LD long double
using namespace std;
const int MAXN = 1e5 + 5;
const long long INF = 1e18;

char poe[30];
int t, n, p, head, tail;
LD l, sum[MAXN], dp[MAXN];

LD qpow(LD x, int y) {
	LD res = 1;
	while (y) {
		if (y & 1) res = res * x;
		x = x * x;
		y >>= 1;
	}
	return res;
}

struct Node { int l, r, pos; } q[MAXN];

LD Abs(LD num) { return num < 0 ? -num : num; }
LD cal(int y, int x) {
	if (y > x) swap(x, y);
	return dp[y] + qpow(Abs(sum[x] - sum[y] + x - y - 1 - l), p);
}

int main() {

	scanf("%d", &t);
	while (t--) {
		scanf("%d %Lf %d", &n, &l, &p);

		for (int i = 1; i <= n; i++) {
			scanf("%s", poe);
			sum[i] = sum[i - 1] + strlen(poe);
		}
		head = 1, tail = 0, q[++tail] = Node{1, n, 0};

		for (int i = 1; i <= n; i++) {

			while (head < tail && q[head].r < i) head++;
			int j = q[head].pos;
			dp[i] = cal(j, i);
			while (head < tail && cal(q[tail].l, i) <= cal(q[tail].l, q[tail].pos)) tail--;

			int l = q[tail].l, r = q[tail].r;
			while (l < r) {
				int mid = (l + r + 1) >> 1;
				// printf("%d %d %d %d\n", i, l, mid, r);
				if (cal(mid, q[tail].pos) > cal(mid, i)) r = mid - 1;
				else l = mid;
			}
			if (l > q[tail].l) q[tail].r = l;
			else tail--;

			q[++tail] = Node{l, n, i};

			// printf("dp[%d] = %.0Lf\n", i, dp[i]);

		}

		if (dp[n] > INF) {
			printf("Too hard to arrange\n");
		} else {
			printf("%.0Lf\n", dp[n]);
		}
		printf("--------------------\n");

	}

	return 0;
}