[bzoj 1563][NOI2009]诗人小G

Description

Input

Output

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

Sample Input

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

108
--------------------
32
--------------------
Too hard to arrange
--------------------
1000000000000000000
--------------------
【样例说明】
前两组输入数据中每行的实际长度均为6,后两组输入数据每行的实际长度均为4。一个排版方案中每行相邻两个句子之间的空格也算在这行的长度中(可参见样例中第二组数据)。每行末尾没有空格。

HINT

总共10个测试点,数据范围满足:

测试点 T N L P
1 ≤10 ≤18 ≤100 ≤5
2 ≤10 ≤2000 ≤60000 ≤10
3 ≤10 ≤2000 ≤60000 ≤10
4 ≤5 ≤100000 ≤200 ≤10
5 ≤5 ≤100000 ≤200 ≤10
6 ≤5 ≤100000 ≤3000000 2
7 ≤5 ≤100000 ≤3000000 2
8 ≤5 ≤100000 ≤3000000 ≤10
9 ≤5 ≤100000 ≤3000000 ≤10
10 ≤5 ≤100000 ≤3000000 ≤10
所有测试点中均满足句子长度不超过30。

Solution

玩具装箱2.0

这下不能把括号拆可了,也就意味着不能进行斜率优化惹,肿么办呢

由玩具装箱给我们的启发是,这个方程式一定满足决策单调性,证明?

用对数组求导然后再正值域上分类讨论即可轻松证明,这里不赘述(其实是我不会QQ图片20160623113051

首先可以很轻松的写出方程式:

f[i]=min\begin{Bmatrix}f(j)+(s[i]-s[j]+i-j-1-L)^{p}\end{Bmatrix}

我们记w[i,j]=(s[i]-s[j]+i-j-1-L)^{p},那么原方程式可化为

f[i]=min\begin{Bmatrix}f(j)+w[i,j]\end{Bmatrix}

学过四边形不等式的犇犇都应该知道接下来我要干嘛了

对于这个w数组,显然满足四边形不等式w[i,j]+w[i+1,j+1]\leq w[i+1,j]+w[i,j+1]

证明:

w[i,j]+w[i+1,j+1]=(s[i]-s[j]+i-j-1-L)^{p}+(s[i+1]-s[j+1]+i-j-1-L)^{p}

w[i+1,j]+w[i,j+1]=(s[i+1]-s[j]+i-j-L)^{p}+(s[i]-s[j+1]+i-j-2-L)^{p}

两式相减,得

(s[i]-s[j]+i-j-1-L)^{p}+(s[i+1]-s[j+1]+i-j-1-L)^{p}-(s[i+1]-s[j]+i-j-L)^{p}+(s[i]-s[j+1]+i-j-2-L)^{p}

考虑到s严格递增,所以上述式子一定\leq0

故原不等式得证。

然后就可以维护一个队列,在队列里二分决策转折点辣

时间复杂度O(n\log n)

 

发表评论