突然想起来 $pow$ 好像比快速幂要慢 , 换成快速幂就过了 .
此贴终 .
```cpp
#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e5+10;
int T,n,l,p,len[MAXN],pre[MAXN]; char S[MAXN][32]; long double dp[MAXN];
#define fi first
#define se second
int h,t; pair<pair<int,int>,int> ar[MAXN];
long double pows(long double k,int v) {
long double res=1;
while(v) {
if(v&1) res*=k;
k*=k,v>>=1;
}
return res;
}
long double omega(int lst,int pos) {
return dp[lst]+pows(abs((long double)(len[pos]-len[lst]+pos-lst-1-l)),p);
}
int bfind(int i,int lst,int l,int r) {
int ans=0;
while(l<=r) {
int mid=l+r>>1;
if(omega(lst,mid)<=omega(i,mid)) ans=mid,l=mid+1; else r=mid-1;
}
return ans;
}
void output(int k) {
if(k==0) return ;
output(pre[k]);
ffor(i,pre[k]+1,k-1) printf("%s ",S[i]); printf("%s\n",S[k]);
}
void work(void) {
scanf("%d %d %d",&n,&l,&p);
ffor(i,1,n) scanf("%s",S[i]),len[i]=strlen(S[i])+len[i-1];
h=1,t=0;
ar[++t]={{1,n},0};
ffor(i,1,n) {
while(ar[h].fi.se<i) h++;
dp[i]=omega(ar[h].se,i),pre[i]=ar[h].se;
ar[h].fi.fi=i+1; if(ar[h].fi.fi>ar[h].fi.se) h++;
int L=-1;
while(h<=t) {
int lst=ar[t].se,l=ar[t].fi.fi,r=ar[t].fi.se;
if(omega(i,l)<=omega(lst,l)) {L=l,t--;continue;}
if(omega(i,r)>=omega(lst,r)) {L=r+1;break;}
L=bfind(i,lst,l,r-1)+1; ar[t].fi.se=L-1; break;
}
if(L<=n) ar[++t]={{L,n},i};
}
if(dp[n]>1e18) printf("Too hard to arrange\n");
else {
printf("%lld\n",(long long)(dp[n]+0.5));
output(n);
}
printf("--------------------\n");
}
int main() {
cin>>T; while(T--) work();
return 0;
}
```
by Purslane_Ma @ 2022-12-22 21:46:51
谔谔
by Chthologist7507 @ 2022-12-23 07:59:21