【题目描述】
小 G 是一个出色的诗人,经常作诗自娱自乐。但是,他一直被一件事情所困扰,那就是诗的排版问题。
一首诗包含了若干个句子,对于一些连续的短句,可以将它们用空格隔开并放在一行中,注意一行中可以放的句子数目是没有限制的。小 G 给每首诗定义了一个行标准长度(行的长度为一行中符号的总个数),他希望排版后每行的长度都和行标准长度相差不远。显然排版时,不应改变原有的句子顺序,并且小 G 不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下,小 G 对于排版中的每行定义了一个不协调度, 为这行的实际长度与行标准长度差值绝对值的$P$次方,而一个排版的不协调度为所有行不协调度的总和。
小 G 最近又作了几首诗,现在请你对这首诗进行排版,使得排版后的诗尽量协调(即不协调度尽量小),并把排版的结果告诉他。
【输入格式】
展开
题目描述
小 G 是一个出色的诗人,经常作诗自娱自乐。但是,他一直被一件事情所困扰,那就是诗的排版问题。
一首诗包含了若干个句子,对于一些连续的短句,可以将它们用空格隔开并放在一行中,注意一行中可以放的句子数目是没有限制的。小 G 给每首诗定义了一个行标准长度(行的长度为一行中符号的总个数),他希望排版后每行的长度都和行标准长度相差不远。显然排版时,不应改变原有的句子顺序,并且小 G 不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下,小 G 对于排版中的每行定义了一个不协调度, 为这行的实际长度与行标准长度差值绝对值的 PP 次方,而一个排版的不协调度为所有行不协调度的总和。
小 G 最近又作了几首诗,现在请你对这首诗进行排版,使得排版后的诗尽量协调(即不协调度尽量小),并把排版的结果告诉他。
【输入格式】
输入文件中的第一行为一个整数$T$,表示诗的数量。
接下来为$T$首诗,这里一首诗即为一组测试数据。每组测试数据中的第一行为三个由空格分隔的正整数$N,L,P$,其中:$N$表示这首诗句子的数目,$L$表示这首诗的行标准长度,$P$的含义见问题描述。
从第二行开始,每行为一个句子,句子由英文字母、数字、标点符号等符号组成(ASCII 码$33~127$,但不包含 -
)。
【输出格式】
于每组测试数据,若最小的不协调度不超过$10^{18}$,则第一行为一个数,表示不协调度。接下来若干行,表示你排版之后的诗。注意:在同一行的相邻两个句子之间需要用一个空格分开。
如果有多个可行解,它们的不协调度都是最小值,则输出任意一个解均可。若最小的不协调度超过$10^{18}$,则输出 Too hard to arrange
。
每组测试数据结束后输出 --------------------
,共20个 -
,-
的 ASCII 码为 45,请勿输出多余的空行或者空格。
$n\le 10^5, l\le 3*10^6, p\le 10$
题解
记$sum[i]$为前$i$句的长度和,$dp[i]$为前$i$句的最小不协调度。 有一个显而易见的DP方程: $dp[i]=\min\limits_{j=1}^{i-1}(dp[j]+|sum[i]-sum[j]+(i-j-1)-l|^p)$直接DP显然是$O(n^2)$的 对于这道题我们实际上可以使用决策单调性优化复杂度。
注意到上面的那个转移方程 每个$dp[i]$通过枚举前面的$i-1$个$j$取最小得到 我们把$dp[i]$取到最小的那个$j$记为$p[i]$,这个东西就叫决策。
如果一个DP满足决策单调性,这就是说这个DP满足$p[1]\le p[2]\le \cdots \le p[n]$。
怎么证明一个DP方程是否满足决策单调性?
一个DP方程可以表示成$dp[i]=\min\limits_{j=1}^{i-1}(dp[j]+w(j,i))$ (这道题中$w(j,i)=|sum[i]-sum[j]+(i-j-1)-l|^p$) ,且对于任意的整数$a,b(a<b)$,都有$w(a,b+1)+w(a+1,b)\ge w(a,b)+w(a+1,b+1)$,那么这个DP方程满足决策单调性。
这道题的DP是满足决策单调性的,证明太长不证了,可以由打表得出结论。
那么这有什么好处呢
我们把最终的$p$数组列出来,大概就长这样:$1,1,2,2,3,3,3,\cdots$
因为它是单调不降的 所以我们可以二分出 对于两个数$a,b$,从哪个$dp[i]$开始 用$a$作为$dp[i]$的决策 不如 用$b$作为$dp[i]$的决策。
比如上面那个$p$数组的例子 从$dp[5]$开始 以$2$作为决策就不如$3$了
那么我们就可以通过维护一个单调队列来维护枚举到的$dp[i]$的最优决策是什么了 队列中的每个元素维护两个值 一个是下标$id$,另一个数$st$表示从$dp[st[i]]$开始到$dp[st[i+1]-1]$为止 决策选择$id[i]$是最优的
具体的说 假设现在正在计算$dp[5]$,$p$数组前四个是$1,1,1,2$那么队列里可能会是这样:
第一个元素$id[1]=1$$st[1]=1$表示从$dp[st[1]]$开始 到$dp[st[2]-1]$为止 选择$1$为决策最优 第二个元素$id[2]=2$$st[2]=4$同理
那么现在要推出$dp[5]$由于选择$1$为决策最优的范围是$st[1]\sim st[2]$也就是$1\sim 4$那么决策$1$对$dp[5]$已经没用了 所以从队头弹出。
此时队头元素的$id$是$2$那么就表明$p[5]=2$$dp[5]$从$dp[2]$转移过来最优 我们让$dp[5]=dp[2]+|sum[5]-sum[2]+(5-2-1)-l|^p$
然后我们要看看$5$作为决策会不会比$2$好 由于决策单调性 我们可以二分出$l(l>5)$表示从$l$开始 决策选择$5$比选择$2$更优 如果此时$l<st[2]$那就说明$5$整个就是比$2$要优的 直接把$2$从队尾弹出
把所有要弹的弹出去之后 就在队尾插入这个新增的元素 基本就和普通的单调队列差不多吧。。。
请结合代码食用(感觉代码写的还是很易懂的)
【代码】
1 |
|