dp真是好玩，有好多有趣且优美的优化。

四边形不等式优化

首先，什么是四边形不等式？
一句话来概括，就是：相交小于包含
一维二维的满足四边形不等式的dp式子都具有决策单调性，都可以被优化
二维的太复杂了,我只写一维的好了
令$w(x,y)$是定义在整数集合上的二元函数，对于$a<=b<=c<=d$,有$w(a,c)+w(b,d)<=w(a,d)+w(b,c)$，则称此函数满足四边形不等式。
但是在dp的时候，这种式子不常出现，对于两个确定的i和j，如何确定该函数满足四边形不等式呢？
有如下的定理:对于$a<b$，有$w(a,b+1)+w(a+1,b)>=w(a+1,b+1)+w(a,b)$成立，则此函数满足四边形不等式。
证明如下：

对于$a<c$,有$w(a,c+1)+w(a+1,c)>=w(a,c)+w(a+1,c+1)$
对于$a+1<c$，有$w(a+1,c+1)+w(a+2,c)>=w(a+1,c)+w(a+2,c+1)$
两式相加，得到$w(a,c+1)+w(a+2,c)>=w(a,c)+w(a+2,c+1)$
以此类推，对任意的$a<=b<=c$，有$w(a,c+1)+w(b,c)>=w(a,c)+w(b,c+1)$
同理，对于任意的$a<=b<=c<=d$,有$w(a,d)+w(b,c)>=w(a,c)+w(b,d)$
$Q.E.D.$

那么，四边形不等式如何优化dp呢？对于一维的dp，我们可以将形如$dp[i]=min_{i=0}^j(dp[j]+w(i,j))$的式子优化，因为它具有决策单调性，于是我们用一个单调队列来维护每个i的最优更新的j，就可以在$O(nlogn)$的复杂度内求解问题。

我们来看一下为什么具有决策单调性

令$p[i]$表示对于点$i$的最优决策点
那么任选$0<=j<i$，$j$更新$i$一定比$p[i]$更新$i$更劣
所以得到式子1:$dp[p[i]]+w(p[i],i)<=dp[j]+w(j,i)$
接着我们任选$i+1<=q<+n$，因为函数$w$满足四边形不等式，所以我们得到
式子2:$w(j,q)+w(p[i],i)>=w(p[i],q)+w(j,i)$
对式子2移项，得:$w(p[i],q)-w(p[i],i)<=w(j,q)-w(j,i)$
与式子1相加，得:$dp[p[i]]+w(p[i],q)<=dp[j]+w(j,q)$
也就是说，以$p[i]$为决策点来转移$q$比以$j$为决策点转移$q$更优
所以对于$p[i]$之前的所有决策点都不如$p[i]$来转移$i$之后的点更优，即决策单调性
$Q.E.D$

那么我们怎么来维护这些决策点呢？用一个单调队列维护即可,单调队列里面用结构体存储决策点
存储决策点的位置,决策点可以优化的点的区间的左端点，右端点。
每次加入一个新的决策点的时候若新加的决策点比一整个决策点可以优化的区间都优秀，就直接将这个决策点出队
如果比这个决策点可以优化的区间都劣，就将当前的决策点扔到单调队列的队尾
否则在这个决策点的可优化区间里二分一个点，使得这个点之前都是这个决策点优化更优，这个点之后都是新加进去的决策点更优，改变队尾结构体里记录的值，将当前的决策点入队即可。

NOI2009诗人小G

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

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

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

输入格式
输入文件中的第一行为一个整数T，表示诗的数量。

接下来为T首诗，这里一首诗即为一组测试数据。每组测试数据中的第一行为三个由空格分隔的正整数N，L，P，其中：N表示这首诗句子的数目，L表示这首诗的行标准长度，P的含义见问题描述。

从第二行开始，每行为一个句子，句子由英文字母、数字、标点符号等符号组成（ASCII码33～127，但不包含’-‘）。

输出格式
于每组测试数据，若最小的不协调度不超过10^18，则第一行为一个数，表示不协调度。接下来若干行，表示你排版之后的诗。注意：在同一行的相邻两个句子之间需要用一个空格分开。

如果有多个可行解，它们的不协调度都是最小值，则输出任意一个解均可。若最小的不协调度超过10^18，则输出“Too hard to arrange”（不含引号）。每组测试数据结束后输出“——————–”（不含引号），共20个“-”，“-”的ASCII码为45，请勿输出多余的空行或者空格。

显然令dp[i]表示前i句诗的最小不协调值，sum[i]为前i句诗的前缀和长度
有状态转移方程:$dp[i]=min_{i=0}^jabs(sum[i]-sum[j]+i-j-1-L)^p$
我们如果证明这个式子可以用四边形不等式优化，就可以O(nlogn)求出答案
设$w(i,j)=abs(sum[i]-sum[j]+i-j-1-L)^p$
那么如果$w(a,b+1)+w(a+1,b)>=w(a+1,b+1)+w(a,b)$，就可以说明它满足四边形不等式
那么只需证明$w(a+1,b)-w(a+1,b+1)>=w(a,b)-w(a,b+1)$即可
令$b1=sum[b]+b-sum[a]-a-l-1,b2=sum[b]+b-sum[a]-a-1-l-1$
只需证明$abs(b2)^p-abs(b2+(a[i+1]+1))^p>=abs(b1)^p-abs(b1+(a[i+1]+1))^p$即可
易得，$b2>b1$,那么只需证明对于任意的常数c,函数$y=abs(x)^p-abs(x+c)^p$单调递减
我太菜了不会证明emmmm，引用算法竞赛进阶指南

当p为奇数，x为负数
原函数为y=-x^p-(x+c)^p，求导，发现y’<=0，所以单调递减
其他情况大力分类讨论

CODE

#include <iostream>
#include <cstdio>
#include <cstring>
using namespace std;
#define ll long long
const double eps=1e-8;
long double ksm(long double a,ll b)
{
    long double tmp=1;
    while(b)
    {
        if(b&1)tmp=tmp*a;
        a=a*a;
        b>>=1;
    }
    return tmp;
}
int n,head,tail,ans[200050];
string stt[200050];
ll sum[200050],p,l;
long double f[200050];
struct node
{
    int j,l,r;
}q[5000050];
long double abss(ll x)
{
    return x<0?-x:x;
}
long double zhi(int j,int i)
{
    return ksm(abss((sum[i]-sum[j])+(i-j-1)-l),p);
}
void print(int n)
{
    if(!n)return;
    int t=ans[n];print(t);
    for(int i=t+1;i<=n;i++)
    {
        cout<<stt[i];
        if(i!=n)putchar(' ');
    }
    printf("\n");
}
int query(int l,int r,int i,int j)
{
    int mid;++r;
    while(l<r)
    {
        mid=(l+r)>>1;
        if(f[j]+zhi(j,mid)>f[i]+zhi(i,mid))l=mid+1;
        else r=mid;
    } 
    return l;
}
int main()
{
    int kkk;
    scanf("%d",&kkk);
    while(kkk--)
    {
        memset(ans,0,sizeof(ans));
        head=1;tail=0;
        scanf("%d%d%d",&n,&l,&p);
        for(int i=1;i<=n;i++)cin>>stt[i],sum[i]=sum[i-1]+stt[i].size();
        f[0]=0;
        for(int i=1;i<=n;i++)
        {
            while(head<=tail && f[i-1]+zhi(i-1,q[tail].l)<=f[q[tail].j]+zhi(q[tail].j,q[tail].l))tail--;
            if(head<=tail)
            {
                int pos=query(q[tail].l,q[tail].r,q[tail].j,i-1);
                if(pos<=n)q[tail].r=pos-1,q[++tail]=(node){i-1,pos,n};
            }
            else q[++tail]=(node){i-1,i,n};
            while(head<=tail && q[head].r<i)++head;
            if(head<=tail)q[head].l=i;
            int pos=q[head].j;
            f[i]=f[pos]+zhi(pos,i),ans[i]=pos;
        }
        if(f[n]-1e18>eps)printf("Too hard to arrange\n");
        else 
        {
            printf("%lld\n",(ll)(f[n]));
            print(n);
        }
        printf("--------------------");
        if(kkk)printf("\n");
    }
    return 0;
}