「BZOJ1563」[NOI2009]诗人小G

Description

小G是一个出色的诗人,经常作诗自娱自乐。但是,他一直被一件事情所困扰,那就是诗的排版问题。

一首诗包含了若干个句子,对于一些连续的短句,可以将它们用空格隔开并放在一行中,注意一行中可以放的句子数目是没有限制的。小G给每首诗定义了一个行标准长度(行的长度为一行中符号的总个数),他希望排版后每行的长度都和行标准长度相差不远。显然排版时,不应改变原有的句子顺序,并且小G不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下,小G对于排版中的每行定义了一个不协调度, 为这行的实际长度与行标准长度差值绝对值的PP次方,而一个排版的不协调度为所有行不协调度的总和。

小G最近又作了几首诗,现在请你对这首诗进行排版,使得排版后的诗尽量协调(即不协调度尽量小),并把排版的结果告诉他。

Input

输入文件中的第一行为一个整数TT,表示诗的数量。

接下来为T首诗,这里一首诗即为一组测试数据。每组测试数据中的第一行为三个由空格分隔的正整数NNLLPP,其中:NN表示这首诗句子的数目,LL表示这首诗的行标准长度,PP的含义见问题描述。
从第二行开始,每行为一个句子,句子由英文字母、数字、标点符号等符号组成(ASCII码3312733\sim 127,但不包含-)。
输出格式:
于每组测试数据,若最小的不协调度不超过101810^{18},则第一行为一个数,表示不协调度。接下来若干行,表示你排版之后的诗。注意:在同一行的相邻两个句子之间需要用一个空格分开。
如果有多个可行解,它们的不协调度都是最小值,则输出任意一个解均可。若最小的不协调度超过101810^{18},则输出Too hard to arrange(不含引号)。每组测试数据结束后输出“--------------------”(不含引号),共2020--的ASCII码为4545,请勿输出多余的空行或者空格。

Output

对于每组数据,若最小的不协调度不超过101810^{18},则第一行一个数表示不协调度若最小的不协调度超过101810^{18},则输出Too hard to arrange(不包含引号)。每个输出后面加--------------------

Sample Input

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
4
4 9 3
brysj,
hhrhl.
yqqlm,
gsycl.
4 9 2
brysj,
hhrhl.
yqqlm,
gsycl.
1 1005 6
poet
1 1004 6
poet

Sample Output

1
2
3
4
5
6
7
8
108
--------------------
32
--------------------
Too hard to arrange
--------------------
1000000000000000000
--------------------

HINT

SOlution

fif_{i}表示前ii个句子得到的最小不协调度。
fi=min{fj+(sisj+ij1)P}f_{i}=\min\{f_j + (s_i - s_j + i - j - 1)^P\}
转移用决策单调性优化转移,用单调队列。
如果队首元素的r<ir < i,弹出
更新答案。
如果末尾元素在ll的取值大于iill出的取值,那么弹出末尾。
二分找到ii的有效区间。
单调性体现在:
对于xxii,如果在midmid的时候有vx<viv_x<v_i,那么mid[l,mid]mid\in[l,mid],都有vx<viv_x <v_i。否则,在mid[mid,r]mid \in [mid,r]中都有vx>viv_x > v_i

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
// luogu-judger-enable-o2
#include<cstdio>
#include<algorithm>
#include<iostream>
#include<cstring>
#include<map>
#include<cmath>
#include<queue>
#include<bitset>
#define mk make_pair
#define fi first
#define se second
#define pii pair<int,int>
#define pb push_back
#define sqr(x) ((x)*(x))
using namespace std;
typedef long long ll;
inline ll read() {ll x = 0; char ch = getchar(), w = 1;while(ch < '0' || ch > '9') {if(ch == '-') w = -1;
ch = getchar();}while(ch >= '0' && ch <= '9') {x = x * 10 + ch - '0';ch = getchar();}return x * w;}
void write(ll x) {if(x < 0) putchar('-'), x = -x;if(x > 9) write(x / 10);putchar(x % 10 + '0');}
inline void writeln(ll x) {write(x);puts("");}
const int N = 102000;
int T;
int n, L, P;
ll s[N], a[N];
int pre[N];
long double f[N];
char str[N][66];
int l[N], r[N], tot;
long double cal(int x, int y) {return f[x] + pow((long double)abs(L - (s[y] - s[x] + y - x - 1)), P);}
int h, t;
struct T {
int l, r, i;
}q[N];
void update(int i) {
/* if(h > t) {
exit(0);
}*/
int l = q[t].l - 1, r = n;
while(r - l > 1) {
int mid = (l + r) >> 1;
if(cal(q[t].i, mid) >= cal(i, mid)) r = mid;
else l = mid;
}
if(cal(q[t].i, r) < cal(i, r)) return; //不能等于号
q[t].r = r - 1;
if(q[t].l > q[t].r) --t;
q[++t].l = r;
q[t].r = n;
q[t].i = i;
}
int main() {
T = read();
while(T--) {
n = read(), L = read(), P = read();
for(int i = 1; i <= n; ++i) {
scanf("%s", str[i]);
a[i] = strlen(str[i]);
s[i] = s[i - 1] + a[i];
}
q[h = t = 1].l = 1;
q[1].r = n;
q[1].i = 0;
for(int i = 1; i <= n; ++i) {
while(h < t && q[h].r < i) ++h;
if(h > t) exit(0);
f[i] = cal(q[h].i, i);
pre[i] = q[h].i;
while(cal(q[t].i, q[t].l) >= cal(i, q[t].l)) --t;
update(i);
}
// for(int i = 1; i <= n; ++i) printf("%d:%lld\n", i, (ll)f[i]);
if(f[n] > 1e18) puts("Too hard to arrange");
else {
writeln(f[n]);
/* tot = 0;
int x = n;
while(x) {
l[++tot] = pre[x] + 1;
r[tot] = x;
x = pre[x];
}
while(tot) {
for(int i = l[tot]; i < r[tot]; ++i)
printf("%s ", str[i]);
puts(str[r[tot]]);
--tot;
}*/
}puts("--------------------");
}
return 0;
}