夏晓光(loveJY)的博客

决策单调性优化

钦定$s_i$为前i个串的前缀和

$f_i=f_j+abs(s_i-s_j-L+(i-j-1))^P$

其中i-j-1是空格的数量

然后我们这个式子就可以$O(n^2)$求,并且得出每个i的最优决策点来输出方案

30pts好成绩,因为还有两个点L很小,所以处理的好一点能拿到50pts

紧接着斜率优化就70pts了

最后我们可以决策单调性优化

根据第一篇博客:导函数单增,求最小值,可以使用单调队列

就是说我们i的决策点每次更新的是队列最后的一段,而计算新数的时候用靠前的一段

导函数单增求最大值用单调栈,就是更新的是靠前的一段而计算的时候也用靠前的一段

也就是说导函数增减和最大小值相同就是队列,否则就是栈

二分的时候有点细节,不要写l=m-1,r=m+1那种,因为我们可能连续一段区间都满足,但我们要的是左端点(lower_bound)

code:

#include<bits/stdc++.h>
#define ll long double
using namespace std;
const int MAXN = 2e5 + 7;
const int P = 1e9 + 7;
int T, n, l, p;
int s[MAXN], que[MAXN], k[MAXN], pr[MAXN];
ll f[MAXN];
char str[MAXN][33];//每组数据字符串

inline ll ksm(ll x, int y) {
	ll ans = 1;
	while(y) {
		if(y & 1)ans = ans * x;
		x = x * x;
		y >>= 1;
	}
	return ans;
}

inline ll calc(int x, int y) {
	// printf("x: %dy: %df[y]:%Lf del:%d P:%d %d %d\n", x, y, f[y], s[x], s[y], abs(s[x] - s[y] - l), p);
	// printf("calc:%d %d??\n", x, y);
	return f[y] + ksm(abs(s[x] - s[y] + (x - y - 1) - l), p);
}

inline int bound(int x, int y) {
	int l = x, r = n + 1, m;
	while(l < r) {
		m = (l + r) >> 1;
		if(calc(m, x) >= calc(m, y)) {
			r = m;
		} else {
			l = m + 1;
		}
	}
	// printf("%d %d %d\n", l, r, ans);
	return r;
}

int main() {
	scanf("%d", &T);
	while(T-- > 0) {
		scanf("%d%d%d", &n, &l, &p);
		memset(s, 0, sizeof(s));
		for(int i = 1; i <= n; ++i) {
			scanf("%s", str[i]);
			s[i] = s[i - 1] + strlen(str[i]);
		}
		// for(int i = 1; i <= n; ++i)printf("%d \n", s[i]);
		int i = 1, h = 1, t = 1;
		for(que[1] = 0; i <= n; ++i) {
			while(h < t && k[h] <= i)
				++h;//k是右端点
			f[i] = calc(i, que[h]);
			// printf("our choice: %Lf %d %d\n", f[i], que[h], i);
			pr[i] = que[h];//记录决策点
			while(h < t && k[t - 1] >= bound(que[t], i))
				--t;//如果右端点大于我们栈内二分的端点
			k[t] = bound(que[t], i);
			que[++t] = i;
		}
		if(f[n] > 1e18)puts("Too hard to arrange");
		else {
			printf("%.0Lf\n", f[n]);
			for(que[t = 0] = i = n; i; que[++t] = i = pr[i]);
			for(; t; --t) {
				for(i = que[t] + 1; i < que[t - 1]; ++i)printf("%s ", str[i]);
				puts(str[i]);
			}
		}
		puts("--------------------");
	}
	return 0;
}