神仙 DP……
朴素转移：\(f_i = \min\limits_{0 \le j < i} (f_j + |sum_i - sum_j + i - j - 1 - L|^P)\)。
其中 \(sum_i\) 表示前 \(i\) 个句子的长度之和，注意要算上空格。
下文中用 \(s_i\) 表示第 \(i\) 个句子的长度。
考虑优化这个式子。
首先要知道决策单调性，即每一个状态的最优决策需要有单调性，一般来说都是单调不降。
这样的话，可以考虑转移完 \(i\) 时，考虑 \(i\) 目前可以作为哪些未来状态的最优决策。
类似珂朵莉树，维护若干个三元组 \((d,l,r)\)，表示 \(d\) 目前是 \(\forall i \in [l,r]\)，\(f_i\) 的最优决策。
出现新的 \(i\) 时，即可在已有的三元组中排除掉比这个差的，最后会找到一个三元组使得 \([l,r]\) 中有一部分优于这个，有一部分劣于这个。
但是因为有决策单调性，所以直接二分找到这个分界点，然后更新。
然后考虑怎么维护这些三元组。
其实是可以直接线段树区间赋值维护决策的，二分也挺方便。
不过可以用单调队列减少常数。
然鹅知道这个有什么用吗……
我们怎么知道它有决策单调性？
（暴力找规律）
于是引入一个东西：四边形不等式。
这个东西通常的定义是：若 \(w(x,y)\) 是一个二元函数，对于任意 \(a < b < c < d\)，都有 \(w(a,d) + w(b,c) \ge w(a,c) + w(b,d)\)，则称 \(w\) 满足四边形不等式。
然后有另一个定义：对于 \(a < b\)，都有 \(w(a,b + 1) + w(a + 1,b) \ge w(a,b) + w(a + 1,b + 1)\)。
这两个互为充要条件，这里就不证了。
接下来有一个定理，如果某 DP 方程长这样：\(f_i = \min\limits_{0 \le j < i}(f_j + w(j,i))\)。
那么当 \(w\) 满足四边形不等式时，\(f\) 有决策单调性。
证明：
\(\forall 1 \le i < k \le n,1 \le j < d_i\)，其中 \(d_i\) 表示 \(f_i\) 的最优决策。
有 \[f_{d_i} + w(d_i,i) \le f_j + w(j,i)\] 根据四边形不等式的定义有 \[w(j,k) + w(d_i,i) \ge w(j,i) + w(d_i,k)\] 移项得 \[w(d_i,k) - w(d_i,i) \le w(j,k) - w(j,i)\] 与前面那个式子相加，得 \[f_{d_i} + w(d_i,k) \le f_j + w(j,k)\] 于是得 \(j < d_k\)，证毕。
那么这题的 \(w(x,y)\) 即 \(|sum_y - sum_x + y - x - 1 - L|^P\)。
我们尝试证明其满足四边形不等式。
即证明 \(\forall a < b,w(a,b + 1) + w(a + 1,b) \ge w(a,b) + w(a + 1,b + 1)\)。
设 \(x = sum_b - sum_a + b - a - 1 - L\)，
原式即 \[|x|^P + |x + s_{b + 1} - s_{a + 1}|^P \le |x + s_{b + 1} + 1|^P + |x - s_{a + 1} - 1|^P\] 移项，设 \(y = sum_{b + 1} - sum_a + b - a - L\)，有 \[|x|^P - |x - s_{a + 1} - 1|^P \le |y|^P - |y - s_{a + 1} - 1|^P\] 显然 \(x < y\)，
问题变成证明对于常正整数 \(c,P\)，\(y = |x|^P - |x - c|^P\) 单调不下降。
考虑对其求导，若 \(y' \ge 0\) 则该命题得证。
分类讨论，首先考虑 \(P\) 为偶数的情况，这种情况显然比较简单，因为可以直接把绝对值去掉。
\[\begin{align*}
y' & = (x^P - (x - c)^P)' \\
& = Px^{P - 1} - P(x - c)^{P - 1} \\
& \ge 0
\end{align*}\]
考虑 \(P\) 为奇数的情况，这时就得分别讨论这两项的正负性。
考虑只有前一项为非负数，即 \(0 \le x\) 但 \(x - c < 0\)。
有 \[\begin{align*}
y' & = (x^P + (x - c)^P)' \\
& = Px^{P - 1} + P(x - c)^{P - 1} \\
\end{align*}\] 在题目中用到的 \(c\) 可以保证 \(x + (x - c) \ge 0\)，所以显然这个也 \(\ge 0\)。
考虑两项都为负数，即 \(x < 0\) 的情况。
有 \[\begin{align*}
y' & = (-x^P + (x - c) ^ P)' \\
& = -Px^{P - 1} + P(x - c)^{P - 1} \\
\end{align*}\] 根据 \(x - c < x\) 有 \(-(x - c) > x\)，所以这个也 \(\ge 0\)。
证毕。
于是用一开头提到的方法做就可以了。
注意 long long 依然不够，要 long double。
把代码中的注释去掉就可以在洛谷上通过了，这是 BZOJ AC 代码。
代码： 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
using namespace std;
const int N = 1e5;
const int LEN = 30;
int T,n,l,p;
inline long double fpow(long double a,int b)
{
long double ret = 1;
for(;b;b >>= 1)
(b & 1) && (ret = ret * a),a = a * a;
return ret;
}
long double f[N + 5];
struct note
{
int x,l,r;
} q[N + 5];
int head,tail,d[N + 5];
long double sum[N + 5];
char s[N + 5][LEN + 5];
inline long double calc(int x,int y)
{
return f[x] + fpow(fabsl(sum[y] - sum[x] + y - x - 1 - l),p);
}
int main()
{
scanf("%d",&T);
for(;T--;puts("--------------------"))
{
scanf("%d%d%d",&n,&l,&p);
for(register int i = 1;i <= n;++i)
scanf("%s",s[i]),sum[i] = sum[i - 1] + strlen(s[i]);
q[head = tail = 1] = (note){0,1,n};
for(register int i = 1;i <= n;++i)
{
for(;head < tail && q[head].r < i;++head);
f[i] = calc(q[head].x,i),d[i] = q[head].x;
if(calc(q[tail].x,q[tail].r) > calc(i,q[tail].r))
{
for(;head < tail && calc(q[tail].x,q[tail].l) >= calc(i,q[tail].l);--tail);
int now,l = q[tail].l,r = n,mid;
while(l <= r)
{
mid = l + r >> 1;
if(calc(q[tail].x,mid) >= calc(i,mid))
r = mid - 1,now = mid;
else
l = mid + 1;
}
q[tail].r = now - 1,q[++tail] = (note){i,now,n};
}
}
if(f[n] <= 1e18)
{
printf("%.0Lf\n",f[n]);
/*tail = 0;
for(register int i = n;i;i = d[i])
q[++tail] = (note){0,d[i] + 1,i};
for(;tail;--tail)
for(register int i = q[tail].l;i <= q[tail].r;++i)
printf("%s%c",s[i]," \n"[i == q[tail].r]);*/
}
else
puts("Too hard to arrange");
}
}