今天考试考了，于是开始糊学决策单调性DP
这是一个完全不会优化DP的人
决策单调性DP的一种优化方法是用单调队列优化
存下{左端点l，右端点r，最优决策点p}的三元组，按照单调队列的通常操作来说：
(0.初始化，将整个序列丢进去)
1.弹队头：弹掉所有不合法的三元组(r<i的)
2.求答案，同时更新队头的左端点
3.弹队尾：
①如果队尾的决策点不如i优，说明队尾这整个三元组当前的决策点太靠前了，直接弹掉
②当弹不掉时，根据决策单调性，队尾这个三元组后面的一部分决策点是i，前面的不是，二分出这个位置来修改。当然如果你发现事实上决策点在l就可以直接把整个都弹了=。=
4.入队(没啥可说的)
1 #include<cmath> 2 #include<cstdio> 3 #include<cstring> 4 #include<algorithm> 5 #define lli long long 6 #define double long double 7 using namespace std; 8 const int N=100005; 9 const lli inf=1e18; 10 struct a 11 { 12 int l,r,p; 13 }que[N]; 14 int T,n,m,k,f,b,top,pre[N],stk[N]; 15 lli len[N]; double dp[N]; char str[N][32]; 16 double Qpow(double x,int k) 17 { 18 if(k==1) return x; 19 double tmp=Qpow(x,k/2); 20 return k%2?tmp*tmp*x:tmp*tmp; 21 } 22 double Calc(int a,int b) 23 { 24 return dp[b]+Qpow(fabs(len[a]-len[b]-m-1),k); 25 } 26 int main() 27 { 28 scanf("%d",&T); 29 while(T--) 30 { 31 scanf("%d%d%d",&n,&m,&k); 32 for(int i=1;i<=n;i++) 33 { 34 scanf("%s",str[i]+1); 35 len[i]=len[i-1]+strlen(str[i]+1)+1; 36 } 37 que[f=b=0]=(a){1,n,0}; 38 for(int i=1;i<=n;i++) 39 { 40 while(f<b&&que[f].r<i) f++; 41 int pt=que[f].p; que[f].l++; 42 dp[i]=Calc(i,pt),pre[i]=pt; 43 while(f<b&&Calc(que[b].l,que[b].p)>=Calc(que[b].l,i)) b--; 44 int lp=que[b].l,rp=que[b].r,ps=rp+1; 45 while(lp<=rp) 46 { 47 int mid=(lp+rp)/2; 48 if(Calc(mid,i)<=Calc(mid,que[b].p)) rp=mid-1,ps=mid; 49 else lp=mid+1; 50 } 51 (ps==que[b].l)?b--:que[b].r=ps-1; 52 if(ps<=n) que[++b]=(a){ps,n,i}; 53 } 54 if(dp[n]>inf) puts("Too hard to arrange"); 55 else 56 { 57 printf("%lld ",(lli)dp[n]),top=0; 58 for(int i=n;i;i=pre[i]) stk[++top]=i; stk[++top]=0; 59 for(int i=top;i;i--) 60 for(int j=stk[i+1]+1;j<=stk[i];j++) 61 { 62 printf("%s",str[j]+1); 63 j==stk[i]?puts(""):putchar(' '); 64 } 65 } 66 puts("--------------------"); 67 } 68 return 0; 69 }