LuoGu1912：[NOI2009]诗人小G

原题传送门
令$su{m}_i$表示第一个短语到第$i$个短语组成的句子长度
$su{m}_i=i-1+{\sum }_{j=1}^{i}strlen(s_j)$
轻松得到一个暴力$dp$:$d{p}_i=min(d{p}_j+(su{m}_i-su{m}_j-L-1{)}^P)$
令$w(i,j)=(su{m}_i-su{m}_j-L-1{)}^P$
则$d{p}_i=min(d{p}_j+w(i,j))$，发现存在决策单调性

然后就是决策单调性的做法

• 单调队列维护，记录决策、临界值，这边临界值的意义是第一个下一个决策比这一个决策优的整点
• 队首决策是相对于当前状态最优的决策，更新
• 二分找到当前决策和前面的临界值，更新单调队列

Code：

#include <bits/stdc++.h>
#define maxn 100010
using namespace std;
char s[maxn][31];
long double dp[maxn];
int h, t, n, L, P, q[maxn], pre[maxn], k[maxn], sum[maxn];

inline int read(){
	int s = 0, w = 1;
	char c = getchar();
	for (; !isdigit(c); c = getchar()) if (c == '-') w = -1;
	for (; isdigit(c); c = getchar()) s = (s << 1) + (s << 3) + (c ^ 48) ;
	return s * w;
} 

long double ksm(long double n, int k){
	if (!k) return 1.0;
	long double sum = ksm(n, k >> 1);
	sum *= sum;
	if (k & 1) sum *= n;
	return sum;
}

long double calc(int i, int j){ return dp[j] + ksm((long double)abs(sum[i] - sum[j] - L - 1), P); }

int find(int j, int i){
	int l = j, r = n + 1, sum = 0;
	while (l <= r){
		int mid = (l + r) >> 1;
		if (calc(mid, j) >= calc(mid, i)) r = mid - 1; else l = mid + 1;
	}
	return l;
}

int main(){
	int M = read();
	while (M--){
		n = read(), L = read(), P = read();
		for (int i = 1; i <= n; ++i) scanf("%s", s[i]), sum[i] = strlen(s[i]) + sum[i - 1] + 1;
		q[h = t = 1] = 0;
		for (int i = 1; i <= n; ++i){
			while (h < t && k[h] <= i) ++h;
			pre[i] = q[h], dp[i] = calc(i, q[h]);
			while (h < t && k[t - 1] >= find(q[t], i)) --t;
			k[t] = find(q[t], i);
			q[++t] = i;
		}
		if (dp[n] > 1e18) puts("Too hard to arrange"); else{
			printf("%lld\n", (long long)dp[n]);
			int cnt = 0;
			for (int i = n; i; i = pre[i]) q[++cnt] = pre[i]; q[0] = n;
			while (cnt--){
				for (int i = q[cnt + 1] + 1; i < q[cnt]; ++i) printf("%s ", s[i]);
				printf("%s\n", s[q[cnt]]);
			}
		}
		puts("--------------------");
	}
	return 0;
}