题目
小G是一个出色的诗人，经常作诗自娱自乐。但是，他一直被一件事情所困扰，那就是诗的排版问题。
一首诗包含了若干个句子，对于一些连续的短句，可以将它们用空格隔开并放在一行中，注意一行中可以放的句子数目是没有限制的。小G给每首诗定义了一个行标准长度（行的长度为一行中符号的总个数），他希望排版后每行的长度都和行标准长度相差不远。显然排版时，不应改变原有的句子顺序，并且小G不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下，小G对于排版中的每行定义了一个不协调度, 为这行的实际长度与行标准长度差值绝对值的P次方，而一个排版的不协调度为所有行不协调度的总和。
小G最近又作了几首诗，现在请你对这首诗进行排版，使得排版后的诗尽量协调（即不协调度尽量小），并把排版的结果告诉他。
思路
需要用到决策单调性中一个叫二分栈（队列）的东西。
转移式子十分显然：
[dp[i]=min(dp[j]+w(j,i))
]
然后打表发现决策是单调的。
重点来了
如何维护决策单调性呢？
决策单调性一般有以下几种维护方法：
- 四边形不等式
- 二分栈（队列）
- CDQ分治套分治
- WQS二分
这里先写一下二分栈（队列）
具体而言，这个队列维护的是区间的决策单调性的信息。队列中的元素有3个权值，(l,r,s)分别表示区间和这个区间对应的决策点。
假设某一状态下的决策点是：
11112222233344444445555566666777777777777777
那么新加入一个决策点8，它就可以从后往前把7，6，5这些可能不如它优的点弹掉。如果不能弹掉一整个块，就二分弹掉它的一部分，这样我们就成功维护了决策单调性了。
复杂度分析
对于每个决策点来说，它只可能进出队列一次，复杂度为(O(n))。
计算每一个(dp[i])，最坏情况下每次都要二分很大的序列，复杂度为(O(nlogn))。
所以总复杂度为(O(nlogn))。
代码
#include<bits/stdc++.h>
#define M 100005
#define LL long double
using namespace std;
const LL inf=1e18;
int n,L,P,T,A[M];
char S[35];
LL sum[M],dp[M];
LL calc(int i,int j){
int y=abs(sum[i]-sum[j]+i-j-1-L);
LL res=1;
for(int i=1;i<=P;i++)res*=y;
return dp[j]+res;
}
struct node{int l,r,s;}Q[M];
int main(){
freopen("poet.in","r",stdin);
freopen("poet.out","w",stdout);
scanf("%d",&T);
while(T--){
scanf("%d%d%d",&n,&L,&P);
for(int i=1;i<=n;i++){
scanf("%s",S);
sum[i]=sum[i-1]+strlen(S);
}
int l=1,r=0;
Q[++r]=(node){1,n,0};
for(int i=1;i<=n;i++){
dp[i]=calc(i,Q[l].s);
if(Q[l].l==Q[l].r)l++;
else Q[l].l++;
while(l<=r&&calc(Q[r].l,Q[r].s)>calc(Q[r].l,i))r--;
if(l>r)Q[++r]=(node){i+1,n,i};
else {
int L=Q[r].l+1,R=Q[r].r+1;
while(L<R){
int mid=(L+R)>>1;
if(calc(mid,Q[r].s)>calc(mid,i))R=mid;
else L=mid+1;
}
Q[r].r=L-1;
if(L<=n)Q[++r]=(node){L,n,i};
}
}
if(dp[n]>1e18)puts("Too hard to arrange");
else printf("%.0Lf
",dp[n]);
puts("--------------------");
}
return 0;
}