题目
题目链接：https://www.luogu.com.cn/problem/P1912
小 G 是一个出色的诗人，经常作诗自娱自乐。但是，他一直被一件事情所困扰，那就是诗的排版问题。
一首诗包含了若干个句子，对于一些连续的短句，可以将它们用空格隔开并放在一行中，注意一行中可以放的句子数目是没有限制的。小 G 给每首诗定义了一个行标准长度（行的长度为一行中符号的总个数），他希望排版后每行的长度都和行标准长度相差不远。显然排版时，不应改变原有的句子顺序，并且小 G 不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下，小 G 对于排版中的每行定义了一个不协调度, 为这行的实际长度与行标准长度差值绝对值的 (P) 次方，而一个排版的不协调度为所有行不协调度的总和。
小 G 最近又作了几首诗，现在请你对这首诗进行排版，使得排版后的诗尽量协调（即不协调度尽量小），并把排版的结果告诉他。
(Tleq 10,nleq 10^5,Lleq 3 imes 10^6,Pleq 10,) 字符串长度 (leq 30)。
思路
记 ( ext{len}_i) 表示字符串的长度前缀和。可以直接把后面的空格长度算进去。
设 (f_i) 表示前 (i) 句诗的最小不协调度，显然有
手画分类讨论一下不难发现，对于 (j<i)，(j) 的决策点一定小于等于 (i) 的决策点。也就是满足四边形不等式。
那么直接用单调队列维护一下就好了。要转移到 (i) 的时候，就不断检查队首，如果队首前两位的函数交点在 (i) 之前就弹出。
插入 (i) 的时候不断检查队尾，如果队尾的两个元素的交点在队尾和 (i) 的交点后就弹出。
判断答案超过 (10^{18}) 可以直接用 long double，这样如果超过了 (10^{18}) 虽然会损失精度导致结果错误，但是正确结果一定是超过 (10^{18})。直接判断无解即可。
时间复杂度 (O(Tnlog n))。
代码
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef long double ld;
const int N=100010;
const ld Inf=1e18;
int Q,n,m,p,hd,tl,g[N],q[N],len[N],pre[N];
ld f[N];
char s[N][32];
ld fpow(ld x,ll k)
{
ld ans=1;
for (;k;k>>=1,x=x*x)
if (k&1) ans=ans*x;
return ans;
}
ld calc(int i,int j)
{
return f[j]+fpow(abs(len[i]-len[j]-1-m),p);
}
int binary(int i,int j)
{
int l=j,r=n,mid;
while (l<=r)
{
mid=(l+r)>>1;
if (calc(mid,i)<calc(mid,j)) l=mid+1;
else r=mid-1;
}
return l-1;
}
void dfs(int n)
{
if (!n) return;
dfs(pre[n]);
for (int i=pre[n]+1;i<n;i++)
printf("%s ",s[i]);
printf("%s
",s[n]);
}
int main()
{
scanf("%d",&Q);
while (Q--)
{
memset(f,0,sizeof(f));
hd=tl=1; q[1]=0;
scanf("%d%d%d",&n,&m,&p);
for (int i=1;i<=n;i++)
{
scanf("%s",s[i]);
len[i]=len[i-1]+strlen(s[i])+1;
}
for (int i=1;i<=n;i++)
{
while (hd<tl && g[q[hd]]<i) hd++;
f[i]=calc(i,q[hd]); pre[i]=q[hd];
while (hd<tl && g[q[tl-1]]>=binary(q[tl],i)) tl--;
g[q[tl]]=binary(q[tl],i); q[++tl]=i;
}
if (f[n]>Inf) printf("Too hard to arrange
");
else printf("%lld
",(ll)f[n]),dfs(n);
printf("--------------------
");
}
return 0;
}