今天考试考了，于是开始糊学决策单调性DP
这是一个完全不会优化DP的人
决策单调性DP的一种优化方法是用单调队列优化
存下{左端点l，右端点r，最优决策点p}的三元组，按照单调队列的通常操作来说：
(0.初始化，将整个序列丢进去)
1.弹队头：弹掉所有不合法的三元组(r<i的)
2.求答案，同时更新队头的左端点
3.弹队尾：
①如果队尾的决策点不如i优，说明队尾这整个三元组当前的决策点太靠前了，直接弹掉
②当弹不掉时，根据决策单调性，队尾这个三元组后面的一部分决策点是i，前面的不是，二分出这个位置来修改。当然如果你发现事实上决策点在l就可以直接把整个都弹了=。=
4.入队(没啥可说的)
#include<cmath>
#include<cstdio>
#include<cstring>
#include<algorithm>
#define lli long long
#define double long double
using namespace std;
const int N=;
const lli inf=1e18;
struct a
{
int l,r,p;
}que[N];
int T,n,m,k,f,b,top,pre[N],stk[N];
lli len[N]; double dp[N]; char str[N][];
double Qpow(double x,int k)
{
if(k==) return x;
double tmp=Qpow(x,k/);
return k%?tmp*tmp*x:tmp*tmp;
}
double Calc(int a,int b)
{
return dp[b]+Qpow(fabs(len[a]-len[b]-m-),k);
}
int main()
{
scanf("%d",&T);
while(T--)
{
scanf("%d%d%d",&n,&m,&k);
for(int i=;i<=n;i++)
{
scanf("%s",str[i]+);
len[i]=len[i-]+strlen(str[i]+)+;
}
que[f=b=]=(a){,n,};
for(int i=;i<=n;i++)
{
while(f<b&&que[f].r<i) f++;
int pt=que[f].p; que[f].l++;
dp[i]=Calc(i,pt),pre[i]=pt;
while(f<b&&Calc(que[b].l,que[b].p)>=Calc(que[b].l,i)) b--;
int lp=que[b].l,rp=que[b].r,ps=rp+;
while(lp<=rp)
{
int mid=(lp+rp)/;
if(Calc(mid,i)<=Calc(mid,que[b].p)) rp=mid-,ps=mid;
else lp=mid+;
}
(ps==que[b].l)?b--:que[b].r=ps-;
if(ps<=n) que[++b]=(a){ps,n,i};
}
if(dp[n]>inf) puts("Too hard to arrange");
else
{
printf("%lld\n",(lli)dp[n]),top=;
for(int i=n;i;i=pre[i]) stk[++top]=i; stk[++top]=;
for(int i=top;i;i--)
for(int j=stk[i+]+;j<=stk[i];j++)
{
printf("%s",str[j]+);
j==stk[i]?puts(""):putchar(' ');
}
}
puts("--------------------");
}
return ;
}