BZOJ 1563.「NOI2009」诗人小 G

神仙 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
#include <cstdio>
#include <cstring>
#include <cmath>
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");
}
}