模板题。
每个决策点都有一个作用区间，后来的决策点可能会比先前的优。于是对于每个决策点二分到它会比谁在什么时候更优，得到新的决策点集合与区间。
1 #include<cstdio> 2 #include<algorithm> 3 #include<cstring> 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)<cal(b,mid)) l=mid+1; else r=mid-1; 27 } 28 return l; 29 } 30 31 void DP(){ 32 int st=1,ed=1; q[1]=(P){0,n,0}; 33 rep(i,1,n){ 34 if (st<=ed && i>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 }