BZOJ 1563.「NOI2009」诗人小 G

神仙 DP……

朴素转移:fi=min0j<i(fj+sumisumj+ij1LP)f_i = \min\limits_{0 \le j < i} (f_j + |sum_i - sum_j + i - j - 1 - L|^P)
其中 sumisum_i 表示前 ii 个句子的长度之和,注意要算上空格。
下文中用 sis_i 表示第 ii 个句子的长度。

考虑优化这个式子。
首先要知道决策单调性,即每一个状态的最优决策需要有单调性,一般来说都是单调不降。
这样的话,可以考虑转移完 ii 时,考虑 ii 目前可以作为哪些未来状态的最优决策。

类似珂朵莉树,维护若干个三元组 (d,l,r)(d,l,r),表示 dd 目前是 i[l,r]\forall i \in [l,r]fif_i 的最优决策。
出现新的 ii 时,即可在已有的三元组中排除掉比这个差的,最后会找到一个三元组使得 [l,r][l,r] 中有一部分优于这个,有一部分劣于这个。
但是因为有决策单调性,所以直接二分找到这个分界点,然后更新。

然后考虑怎么维护这些三元组。
其实是可以直接线段树区间赋值维护决策的,二分也挺方便。
不过可以用单调队列减少常数。

然鹅知道这个有什么用吗……
我们怎么知道它有决策单调性?
(暴力找规律)

于是引入一个东西:四边形不等式。
这个东西通常的定义是:若 w(x,y)w(x,y) 是一个二元函数,对于任意 a<b<c<da < b < c < d,都有 w(a,d)+w(b,c)w(a,c)+w(b,d)w(a,d) + w(b,c) \ge w(a,c) + w(b,d),则称 ww 满足四边形不等式
然后有另一个定义:对于 a<ba < b,都有 w(a,b+1)+w(a+1,b)w(a,b)+w(a+1,b+1)w(a,b + 1) + w(a + 1,b) \ge w(a,b) + w(a + 1,b + 1)
这两个互为充要条件,这里就不证了。

接下来有一个定理,如果某 DP 方程长这样:fi=min0j<i(fj+w(j,i))f_i = \min\limits_{0 \le j < i}(f_j + w(j,i))
那么当 ww 满足四边形不等式时,ff 有决策单调性。

证明:
1i<kn,1j<di\forall 1 \le i < k \le n,1 \le j < d_i,其中 did_i 表示 fif_i 的最优决策。

fdi+w(di,i)fj+w(j,i)f_{d_i} + w(d_i,i) \le f_j + w(j,i)

根据四边形不等式的定义有

w(j,k)+w(di,i)w(j,i)+w(di,k)w(j,k) + w(d_i,i) \ge w(j,i) + w(d_i,k)

移项得

w(di,k)w(di,i)w(j,k)w(j,i)w(d_i,k) - w(d_i,i) \le w(j,k) - w(j,i)

与前面那个式子相加,得

fdi+w(di,k)fj+w(j,k)f_{d_i} + w(d_i,k) \le f_j + w(j,k)

于是得 j<dkj < d_k,证毕。

那么这题的 w(x,y)w(x,y)sumysumx+yx1LP|sum_y - sum_x + y - x - 1 - L|^P
我们尝试证明其满足四边形不等式。
即证明 a<b,w(a,b+1)+w(a+1,b)w(a,b)+w(a+1,b+1)\forall a < b,w(a,b + 1) + w(a + 1,b) \ge w(a,b) + w(a + 1,b + 1)

x=sumbsuma+ba1Lx = sum_b - sum_a + b - a - 1 - L
原式即

xP+x+sb+1sa+1Px+sb+1+1P+xsa+11P|x|^P + |x + s_{b + 1} - s_{a + 1}|^P \le |x + s_{b + 1} + 1|^P + |x - s_{a + 1} - 1|^P

移项,设 y=sumb+1suma+baLy = sum_{b + 1} - sum_a + b - a - L,有

xPxsa+11PyPysa+11P|x|^P - |x - s_{a + 1} - 1|^P \le |y|^P - |y - s_{a + 1} - 1|^P

显然 x<yx < y
问题变成证明对于常正整数 c,Pc,Py=xPxcPy = |x|^P - |x - c|^P 单调不下降。

考虑对其求导,若 y0y' \ge 0 则该命题得证。
分类讨论,首先考虑 PP 为偶数的情况,这种情况显然比较简单,因为可以直接把绝对值去掉。

考虑 PP 为奇数的情况,这时就得分别讨论这两项的正负性。
考虑只有前一项为非负数,即 0x0 \le xxc<0x - c < 0

在题目中用到的 cc 可以保证 x+(xc)0x + (x - c) \ge 0,所以显然这个也 0\ge 0

考虑两项都为负数,即 x<0x < 0 的情况。

根据 xc<xx - c < x(xc)>x-(x - c) > x,所以这个也 0\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");
}
}