原汁原味的代码,处于不太理智的情况下改了一堆地方,题解讨论区都看了,还是馬锝30pts……
```cpp
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define lb long double
//草泥马为什么开lb
const ll N=5*1145140,M=1919810,inf=1145141919810000000;
ll tt,n,L; string str[N];
lb dp[N],p;
lb q[N],a[N],sum[N];
lb l[N],pos[N];
lb qpow(lb a,ll b){ //馬锝
lb ans=1;
while(b){
if(b&1) ans*=a;
a*=a;
b>>=1;
}
return ans;
}
/*dp[i]=min(dp[i],dp[j]+qpow(abs(sum[i]-sum[j]+i-j-1-L),p))*/
ll work(ll i,ll j){
return dp[j]+qpow(abs(sum[i]-sum[j]+i-j-1-L),p);
}
ll binary(ll x,ll y){
ll l=x,r=n+1,mid;
while(l<r){
mid=(l+r)>>1;
if(work(mid,x)>=work(mid,y)) r=mid;
else l=mid+1;
}
return l; //馬锝
}
void out(ll now){
if(!now) return;
out(pos[now]);
for(int i=pos[now]+1;i<now;++i) cout<<str[i]<<" "; //不能多输空格
cout<<str[now]<<'\n';
}
//快疯了
int main(){
/*ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);傻逼*/
cin>>tt;
while(tt--){
//????????????
cin>>n>>L>>p;
for(int i=1;i<=n;++i){
cin>>str[i],a[i]=str[i].size();
sum[i]=sum[i-1]+a[i];
//dp[i]=inf;
}
ll h=1,t=1; //妈的我是傻逼
q[h]=0;
for(int i=1;i<=n;++i){
while(h<t&&l[h]<=i) ++h;
pos[i]=q[h];
dp[i]=work(i,pos[i]); //dp
while(h<t&&l[t-1]>=binary(q[t],i)) --t; //把劣的队尾退了
l[t]=binary(q[t],i);
q[++t]=i; //入队
}
if(dp[n]>1e18) cout<<"Too hard to arrange\n";
else{
printf("%.0Lf\n",dp[n]); //傻逼
out(n);
}
cout<<"--------------------\n";
}
return 0;
}
```
by mzycの喰种 @ 2023-09-08 19:18:41
so,为什么多测不清空?
by Dovish @ 2023-09-08 19:29:46
好罢,试了一下没用
by Dovish @ 2023-09-08 19:36:53
重构已过,还是不知道错哪里了
by mzycの喰种 @ 2023-09-09 11:25:03
默哀
by programfor @ 2024-02-17 08:45:34
太文明啦
by linmou @ 2024-02-17 08:53:11
默哀
by distjr_ @ 2024-02-17 09:41:53
被封禁了
by lzy20120716 @ 2024-02-22 21:07:52