P1912求调试玄关

#include<bits/stdc++.h>
using namespace std;
#define LD long double
#define N 100005
LD T,l,p,s[N],f[N];
int h,t,n;
struct data{
	int k,a,b;
}q[N];
LD fast_pow(LD x,int y){
	LD res=1,st=x;
	while(y){
		if(y&1)res*=st;
		st*=st,y>>=1;
	}
	return res;
}
LD calc(int i,int j){
	return f[j]+fast_pow(abs(s[i]-s[j]-l-1),p);
}
int bound(int u,int v,int x,int y){
	int res=v+1;
	while(u<=v){
		int mid=u+v>>1;
		if(calc(mid,x)<=calc(mid,y)){
			res=mid,v=mid-1;
		}
		else u=mid+1;
	}
	return res;
}
int main(){
	cin.tie(0),cout.tie(0);
	cin>>T;
	while(T--){
		cin>>n>>l>>p;
		memset(f,0,sizeof(f));
		memset(q,0,sizeof(q));
		memset(s,0,sizeof(s));
		for(int i=1;i<=n;i++){
			string o;
			cin>>o;
			s[i]=s[i-1]+o.size()+1;
		}
		h=t=1;
		for(int i=1;i<=n;i++){
			while(h<t&&q[h+1].b<i)h++;
			f[i]=calc(i,q[h+1].k);
			cout<<q[h+1].k<<"\n";
			if(h<t)q[h+1].a=i;
			int pos=i+1;
			while(h<t&&calc(q[t].a,i)<=calc(q[t].a,q[t].k))pos=q[t].a,t--;
			if(h<t){
				int pos=bound(q[t].a,q[t].b,i,q[t].k);
				q[t].b=pos-1;
			}
			data m;
			m.a=pos,m.b=n,m.k=i;
			q[++t]=m;
		}
		cout<<f[n]<<"\n";
	}
	return 0;
}