模板题。

每个决策点都有一个作用区间，后来的决策点可能会比先前的优。于是对于每个决策点二分到它会比谁在什么时候更优，得到新的决策点集合与区间。

1 #include
     
       2 #include
      
        3 #include
       
         4 #define rep(i,l,r) for (int i=(l); i<=(r); i++) 5 typedef long double ll; 6 using namespace std; 7  8 const int N=100010; 9 const ll MAX=1e18;10 int T,n,l,p,top;11 ll sm[N],f[N];12 char ch[N][35];13 struct P{ int l,r,p; }q[N];14 15 ll ksm(ll x){16     if (x<0) x=-x;17     ll res=1; rep(i,1,p) res*=x; return res;18 }19 20 ll cal(int j,int i){ return f[j]+ksm(sm[i]-sm[j]+(i-j-1)-l); }21 22 int find(P a,int b){23     int l=a.l,r=a.r;24     while (l<=r){25         int mid=(l+r)>>1;26         if (cal(a.p,mid)
        
         q[st].r) st++;35         f[i]=cal(q[st].p,i);36         if (st>ed || cal(i,n)<=cal(q[ed].p,n)){37             while (st<=ed && cal(i,q[ed].l)<=cal(q[ed].p,q[ed].l)) ed--;38             if (st>ed) q[++ed]=(P){i,n,i};39             else{40                 int t=find(q[ed],i);41                 q[ed].r=t-1; q[++ed]=(P){t,n,i};42             }43         }44     }45 }46 47 int main(){48     freopen("bzoj1563.in","r",stdin);49     freopen("bzoj1563.out","w",stdout);50     for (scanf("%d",&T); T--; ){51         scanf("%d%d%d",&n,&l,&p);52         rep(i,1,n) scanf("%s",ch[i]);53         rep(i,1,n) sm[i]=sm[i-1]+strlen(ch[i]);54         DP();55         if (f[n]>MAX) printf("Too hard to arrange\n");56             else printf("%lld\n",(long long)(f[n]));57         puts("--------------------");58     }59     return 0;60 }