题目

小G是一个出色的诗人，经常作诗自娱自乐。但是，他一直被一件事情所困扰，那就是诗的排版问题。

一首诗包含了若干个句子，对于一些连续的短句，可以将它们用空格隔开并放在一行中，注意一行中可以放的句子数目是没有限制的。小G给每首诗定义了一个行标准长度（行的长度为一行中符号的总个数），他希望排版后每行的长度都和行标准长度相差不远。显然排版时，不应改变原有的句子顺序，并且小G不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下，小G对于排版中的每行定义了一个不协调度, 为这行的实际长度与行标准长度差值绝对值的P次方，而一个排版的不协调度为所有行不协调度的总和。

小G最近又作了几首诗，现在请你对这首诗进行排版，使得排版后的诗尽量协调（即不协调度尽量小），并把排版的结果告诉他。

思路

需要用到决策单调性中一个叫二分栈（队列）的东西。

转移式子十分显然：
\[ dp[i]=min(dp[j]+w(j,i)) \]
然后打表发现决策是单调的。

重点来了

如何维护决策单调性呢？

决策单调性一般有以下几种维护方法：

  1. 四边形不等式
  2. 二分栈（队列）
  3. CDQ分治套分治
  4. 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\n",dp[n]);
        puts("--------------------");       
    }
    return 0;
}