题目描述：
算法标签：dp，决策单调性
思路：
求导证明dp式子具有决策单调的性质，其他应该是常规操作吧...看看代码应该能懂。
小提示：要用long double存不然会死。
以下代码：
#include<bits/stdc++.h> #define il inline #define LL long long #define db long double #define _(d) while(d(isdigit(ch=getchar()))) using namespace std; const int N=1e5+5; char s[N]; int n,sum[N],L,P,l,r;db f[N]; struct node{int l,r,p;}q[N]; il int read(){ int x,f=1;char ch; _(!)ch=='-'?f=-1:f;x=ch^48; _()x=(x<<1)+(x<<3)+(ch^48); return f*x; } il db ksm(db a,int y){ a=fabs(a);db b=1; while(y){ if(y&1)b*=a; a*=a;y>>=1; } return b; } il db cal(int j,int i){ return f[j]+ksm(sum[i]-sum[j]+i-j-1-L,P); } int main() { //freopen("get_data.htm","r",stdin); int T=read();while(T--){ n=read();L=read();P=read();bool pd=0; for(int i=1;i<=n;i++){ scanf(" %s",s); int ll=strlen(s); sum[i]=sum[i-1]+ll; } q[l=r=1]=(node){1,n,0}; for(int i=1;i<=n;i++){ if(q[l].r<i)l++; f[i]=cal(q[l].p,i); while(l<=r&&q[r].l>i&&cal(i,q[r].l)<=cal(q[r].p,q[r].l))r--; int ll=max(i,q[r].l),rr=q[r].r; while(ll<rr){ int mid=(ll+rr+1)>>1; if(cal(q[r].p,mid)<cal(i,mid))ll=mid;else rr=mid-1; } q[r].r=ll;if(ll<n)q[++r]=(node){ll+1,n,i}; } if(f[n]>1e18)puts("Too hard to arrange"); else printf("%lld ",(LL)(f[n]+0.5));puts("--------------------"); } return 0; }