C++(g++ 7.5.0) 解法, 执行用时: 165ms, 内存消耗: 3008K, 提交时间: 2022-08-12 13:00:44

#include <bits/stdc++.h>
#define M 100100
#define LIMIT 1000000000000000000ll
using namespace std;
typedef long double ld;
int n,l,p;
int sum[M],g[M],st[M],top;
ld f[M];
long double Slow_Power(long double x,int y)
{
    long double re=1;
    for(int i=1;i<=y;i++)
        re*=x;
    return re;
}
int Get_Len()
{
    static char s[40];
    scanf("%s",s+1);
    return strlen(s+1);
}
int Get_Pos(int x)
{
    int l=1,r=top;
    while(r-l>1)
    {
        int mid=l+r>>1;
        if( g[st[mid]]<=x )
            l=mid;
        else
            r=mid;
    }
    return g[st[r]]<=x?r:l;
}
ld F(int j,int i)
{
    return f[j]+Slow_Power(fabs(sum[i]-sum[j]+(i-j-1)-l),p);
}
int Get_G(int x,int y)
{
    int l=max(g[x],y)+1,r=n+1;
    while(r-l>1)
    {
        int mid=l+r>>1;
        if( F(y,mid) < F(x,mid) )
            r=mid;
        else
            l=mid;
    }
    if(l==r) return r;
    return F(y,l) < F(x,l) ? l : r ;
}
int main()
{
    int T,i;
    for(cin>>T;T;T--)
    {
        cin>>n>>l>>p;
        for(i=1;i<=n;i++)
            sum[i]=sum[i-1]+Get_Len();
        g[0]=1;st[top=1]=0;
        for(i=1;i<=n;i++)
        {
            int pos=st[Get_Pos(i)];
            f[i]=F(pos,i);
            while( g[st[top]]>i && F(i,g[st[top]]) < F(st[top],g[st[top]]) )
                st[top--]=0;
            pos=Get_G(st[top],i);
            if(pos!=n+1)
            {
                st[++top]=i;
                g[i]=pos;
            }
        }
        if(f[n]-0.5>LIMIT)
            puts("Too hard to arrange");
        else
            cout<<(long long)(f[n]+0.5)<<endl;
        puts("--------------------");
    }
    return 0;
}

C++ 解法, 执行用时: 503ms, 内存消耗: 6544K, 提交时间: 2022-02-02 14:27:46

#include<bits/stdc++.h>
#define cc(i,j) f[j]+qpow(abs(s[i]-s[j]-L))
using namespace std;
int n,L,P,s[100001],q[100001],k[100001],pr[100001],r,h,y,T,i,t;
long double f[100001];
char str[100001][33];
long double qpow(long double b){long double a=1;for(int k=P;k;k>>=1,b*=b)if(k&1)a*=b;return a;}
int bound(int x,int y){int l=x,r=n+1,m;while(l<r)m=(l+r)>>1,cc(m,x)>=cc(m,y)?r=m:l=m+1;return l;}
int main(){
	cin>>T;
    while(T--){
    	cin>>n>>L>>P;
    	L++;
        for(i=1;i<=n;++i){if(cin>>str[i]);s[i]=s[i-1]+strlen(str[i])+1;}
        for(q[i=h=t=1]=0;i<=n;++i){
            while(h<t&&k[h]<=i)++h;
            f[i]=cc(i,q[h]);
			pr[i]=q[h];
            while(h<t&&k[t-1]>=bound(q[t],i))t--;
            k[t]=bound(q[t],i);
			q[++t]=i;
        }
        if(f[n]>1e18)cout<<"Too hard to arrange\n";
        else{
            printf("%.0Lf\n",f[n]);
            for(q[t=0]=i=n;i;q[++t]=i=pr[i]);
        }
        cout<<"--------------------\n";
    }
    return 0;
}