感觉取min对最优决策没有影响呀。

实测改成long double ,不取min就过了

#include<bits/stdc++.h>
using namespace std;
#define IOS {cin.tie(0);cout.tie(0);ios::sync_with_stdio(0);}
#define rep(i,j,k) for(int i=j;i<=k;++i)
#define per(i,j,k) for(int i=j;i>=k;--i)
#define P pair<int,int>
#define ll long long
#define vi vector<int>
#define ls i<<1,l,mid
#define rs i<<1|1,mid+1,r
#define mi int mid=l+r>>1;
#define lll __int128
const ll inf=1000000000000000001;
ll qp(lll x,int y){
    lll res=1;
    while(y){
        if(y&1)res=min(res*x,(lll)inf);
        x=min(x*x,(lll)inf);
        y>>=1;
    }
    return res;
}
const int N=1e5+5;
string s[N];
int sum[N],d[N],p,L,n;
ll dp[N];  //dp表示值,d表示决策点
P q[N];  //队列维护决策区间,first表示左端点,second表示下标
ll cal(int l,int r){
    return qp(abs(sum[r]-sum[l-1]+r-l-L),p);
}
ll f(int i,int x){
    return min(dp[i]+cal(i+1,x),inf);
}
int crs(int i,int j,int l){
    int r=n,mid;
    while(l<=r){
        mid=l+r>>1;
        if(f(i,mid)>=f(j,mid))r=mid-1;
        else l=mid+1;
    }
    return l;
}
void slv(){
    cin>>n>>L>>p;
    assert(p>=0);
    rep(i,1,n){
        cin>>s[i]; sum[i]=sum[i-1]+s[i].size();
    }
    int l=1,r=1; q[1]={1,0};
    rep(i,1,n){
        // rep(j,l,r)cout<<q[j].second<<" "<<q[j].first<<" hh "; cout<<endl;
        while(l<r && q[l+1].first<=i)++l;
        dp[i]=f(q[l].second,i); d[i]=q[l].second;
        // ll v1=f(q[l].second,i),v2=dp[i]+qp(abs(0-L),p); //sum=0,从0开始,而不是贡献为0!!
        // if(v1>=v2){
        //     q[1]={i+1,i}; l=r=1; continue;
        // }
        while(r>l && f(q[r].second,q[r].first)>=f(i,q[r].first))--r;
        int x=crs(q[r].second,i,max(i+1,q[r].first));
        if(x<=n)q[++r]={x,i};
    }
    if(dp[n]>=inf){
        cout<<"Too hard to arrange\n--------------------\n"; return;
    }
    // rep(i,1,n)cout<<d[i]<<" ";return;
    cout<<dp[n]<<'\n';
    r=0;
    for(int i=n;i;i=d[i])q[++r]={d[i]+1,i};
    per(i,r,1){
        rep(j,q[i].first,q[i].second)cout<<s[j]<<" \n"[j==q[i].second];
    }
    cout<<"--------------------\n";
}
int main(){
    IOS
    int T;cin>>T;
    while(T--)slv();
}