思路：
转移方程： f[i]=f[j]+∣sum[i]−sum[j]−L−1∣ ^P
如果只是暴力枚举， O(N^2) 的复杂度，期望的分：30
考虑怎么优化，打表发现，如果每次把转移i的最优j存储下来，那么输出发现j是单增的，证明不太好证，有兴趣可以去洛谷康一康，下面是感性理解：
设j到i后面的句子组成了新的一行，如果j不单调上升，那么后面的句子有可能会变得很长很长，这时候不协调度将会几何数形式上升，唯一的解决方案就是长句断句，所以j就会变大
如果知道j是单调上升的，那么我们每次转移的时候就不需要往前找了，只需要往后找（可以采用单调队列优化）
维护一个队列，队列里面有三个变量l r c ，其中l r表示c这个决策的适用范围，并且在这个范围中c是最优的j
如果现在有了一个新的i，考虑如何维护这个队列
可以先找到对头的元素，如果发现对头元素已经不包括i了，那么直接弹出
之后直接取对头元素O（1）转移
现在考虑将i加入队列，或许这个i会对后面的元素产生贡献
我们检查队尾元素，如果在队尾元素的范围之内，i更新l比c更新l更优，由于满足决策单调性，所以l后面的元素从i转移比从j转移更优，所以弹出队尾
那么假设现在碰到了一个队尾，其中i更新r更优，c更新l更优，也就是说这个元素中分成两半，前一半更新c更优，后一半i更新更优，那么这显然要拆成两个队列元素，我们怎么知道这个位置呢？二分处理
这个时候我们就可以知道答案了，但是输出怎么办呢？
转移的时候记录一下转移自哪里，这就是分行，然后输出即可
最后是精度问题：
如果在dp是用long long会GG，所以我们使用long double，（整数部分和小数部分一共19位）精度更高
代码：
#include<bits/stdc++.h>
#define ll long long
#define ld long double
using namespace std;
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];
inline ll read()//快读
{
char c=getchar();
ll x=0,f=1;
while(!isdigit(c)){if(c=='-')f=-1;c=getchar();}//不需要判负删掉来简化
while(isdigit(c))x=(x<<3)+(x<<1)+(c^48),c=getchar();
return x*f;
}
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)//dp
{
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;//如果i更优
//那么我们就知道对于mid~rs都是用i更新更优，所以c更新更优的左限制更新到mid-1
else ls=mid+1;//c更优，那么 c更新更优的右限制更新到mid+1
}
if(ret!=q[tail].l ) q[tail].r =ret-1;//如果发现用i更新只能使tail区间内的一部分
//更优，那么就讲tail分成两半
else --tail;//不然，就说明整个元素都比不过i
if(ret<=n) q[++tail]=(node){i,ret,n};//i分了一个新区间
}
void putout()
{
if(f[n]>1e18) puts("Too hard to arrange");
else
{
printf("%lld
",(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
",s[now]);
i=now;
}
}
puts("--------------------");
return;
}
int main()
{
t=read();
while(t--)
{
clear();
n=read(),l=read(),p=read();
for(int i=1;i<=n;i++)
{
scanf("%s",s[i]);
sum[i]=sum[i-1]+strlen(s[i])+1;//前缀和
/*输出有空格,+1*/
}
q[head=tail=1]=(node){0,1,n};//初始元素，0表示最优决策，1~n表示决策范围
for(int i=1;i<=n;i++)
{
while(head<tail&&q[head].r <i) ++head;
//如果对头元素不包括i，弹出队头
++q[head].l ;// ???
f[i]=val(q[head].c,i);//o(1)转移
last[i]=q[head].c ;//记录从哪里转移
while(head<tail&&val(i,q[tail].l )<=val(q[tail].c ,q[tail].l )) tail--;
half(i);
}
putout();
}
return 0;
}