神奇的题目 QvQ ,卡了我好久。
哎,主要是细节要处理到位,否则就会 WA 声满片。
记录一下我壮观的提交记录:

太杯具了 QvQ
(扯谈扯不下去了…….)
进入正题吧。
路人甲:bzoj 上居然没有这道题?
导演:赶紧走开,不管你的事
这题明显是 DP,我们可以很简单的得到 DP 方程:
设 f[i] 表示对前 i 句诗排版后的最小不协调度,那么很显然,对于一个现在我们需要转移的 i,我们会找到一个最优的 j ,使得第 j+1 句到第 i 句组成一个新的行。那么之前的行的总共的最小不协调度显然是 f[j],现在我们就来计算一下 f[i] 的最小不协调度。
显然,是下式 (其中 sum 是句子长度的前缀和):
f[i]=f[j]+|sum[i]−sum[j]−L−1|P
这就是状态转移方程,的确很好理解。但是…… 这样子做是 O(N2) 的复杂度,只能拿 30 分。
而按照题目的数据范围,正解的复杂度因该是 O(nlogn) 左右。接下来考虑怎么优化。
经打表观察发现,如果我们将每次用作转移 i 的最优的 j 存起来,输出时会发现,j 是单调递增的。
证明的话的确不好证,可以看看 lyd 的书。但是按照实际理解一下是可以的,我们将 j 后面的一直到 i 的句子组成了新的一行,那么如果 j 不单调上升的话,新的一句将会变的很长很长很长,那么这时这句造成的不协调度将会以几何数的形式疯狂增长,那么唯一的方法就是将这句长句断句,这样子 j 就会变大,可以感性理解一下 QvQ。
但是我们知道了 j 是单调上升的这条性质有什么用呢?
很显然,每一次转移的时候不必往前找了,直接往后找。
我们维护一个队列,队列里的每一个元素有三个变量:l,r,c ,其中 l 和 r 表示 c 这个决策的适用范围,并且在这个范围中 c 是最优的 j。
那么现在有了一个新的 i,考虑怎么维护这个队列。
我们可以先找到 i 所在的范围的最优的 j,那么这时我们检查队头,如果队头的范围已经不包括 i 了,那么直接弹出,因为既然队头的范围不包括 i 了,那么这个队头对 i+1 及后面的元素都不能产生贡献,故直接弹出。
弹出无用的队头后,转移的话就是 O(1) 了:直接取队头转移不就好了吗?
那么现在考虑怎么将 i 加入这个队列,或许这个 i 也会对后面的元素产生贡献。
我们检查当前的队尾,怎么判断这个队尾是否比 i 更优呢?现在队尾的范围是 l,r ,如果 i 更新 l 比 c 更新 l 更优,显然 i 会比当前 l,r 范围类的所有的 c 更优,故弹出队尾。
那么,假设现在我们碰到了一个队尾,其中 i 更新 r 更优, c 更新 l 更优,怎么办呢?也就是说这个元素的范围中分成两半,前一半 c 更新更优,后一半 i 更新更优,显然要拆成两个队列元素。那么我们怎么知道这个位置呢?二分!
那么这个时候我们可以得到答案了,只是输出怎么办呢?
很简单,每次转移的时候记录一下转移自哪里,这就是分行,然后输出即可。
最后就是精度问题。
题目要求,如果 f[n] (即所有句子排版后的最小不协调度) 还是大于了 1e18 ,那么输出 “Too hard to arrange”,但是如果在 DP 的过程中就炸了 long long,那就 GG 了。所以我们使用 long double ,精度更高,(不会 int 的,这辈子也不会用 int 的)。
Code:
#include<cmath>
#include<cstdio>
#include<string>
#include<cstring>
#include<iostream>
#include<algorithm>
typedef long long ll;
typedef long double ld;
const int NS=1e5+2;
const int inf=1e9+9;
int T,N,L,P;
int head,tail;
int last[NS],ans[NS],Next[NS];
struct Node{int c,l,r;}q[NS];
char s[NS][35];
ld sum[NS],f[NS];
template <typename _Tp> inline void IN(_Tp&x){
char ch;bool flag=0;x=0;
while(ch=getchar(),!isdigit(ch))if(ch=='-')flag=1;
while(isdigit(ch))x=x*10+ch-'0',ch=getchar();
if(flag)x=-x;
}
void clear(){
memset(last,0,sizeof(last));
memset(sum,0,sizeof(sum));
memset(q,0,sizeof(q));
memset(s,0,sizeof(s));
memset(f,0,sizeof(f));
}
ld pows(ld x,int y){
ld ans=1;
for(;y;y>>=1,x*=x)if(y&1)ans*=x;
return ans;
}
ld val(int j,int i){
return f[j]+pows(abs(sum[i]-sum[j]-L-1),P);
}
void half(int i){
int now=q[tail].c,ls=q[tail].l,rs=q[tail].r;
int ret=q[tail].r+1;
while(ls<=rs){
int mid=(ls+rs)>>1;
if(val(i,mid)<=val(now,mid))rs=mid-1,ret=mid;
else ls=mid+1;
}
if(ret!=q[tail].l)q[tail].r=ret-1;
else --tail;
if(ret<=N)q[++tail]=(Node){i,ret,N};
}
void output(){
if(f[N]>1e18)puts("Too hard to arrange");
else{
printf("%lld\n",(ll)(f[N]+0.5));
for(int i=N;i;i=last[i])Next[last[i]]=i;
int now=0;
for(int i=1;i<=N;++i){
now=Next[now];
for(int j=i;j<now;++j)printf("%s ",s[j]);
printf("%s\n",s[now]);
i=now;
}
}
puts("--------------------");
return;
}
int main(){
IN(T);
while(T--){
clear();
IN(N),IN(L),IN(P);
for(int i=1;i<=N;++i){
scanf("%s",s[i]);
sum[i]=sum[i-1]+strlen(s[i])+1;
}
q[head=tail=1]=(Node){0,1,N};
for(int i=1;i<=N;++i){
while(head<tail&&q[head].r<i)++head;
++q[head].l;
f[i]=val(q[head].c,i);
last[i]=q[head].c;
while(head<tail&&val(i,q[tail].l)<=val(q[tail].c,q[tail].l))tail--;
half(i);
}
output();
}
return 0;
}
最后,我有个问题。
这是写的什么文章啊 QvQ ,让我们来猜测一下。

白日依山尽,黄河入海流,欲穷千里目,更上一层楼。
这是 小 G 写的?作者明明不是小 G 好不好。
QvQ 有毒啊……
2 条评论
quhengyi11 · 2019年2月25日 9:57 下午
qwq 问个文题无关的问题
luogu 的 material 化不是自从换了主页之后咕掉了喵
您的背景是怎么搞的 QAQ
Qiuly · 2019年2月26日 7:06 下午
学长,这个问题的话,网上是有文章的。
我是按这个文章设置的:https://www.luogu.org/blog/zhyan/luo-gu-bei-jing