f[i] = min(f[j] + val(i,j);
其中val(i,j) 满足 四边形dp策略。
代码：
#include<bits/stdc++.h>
using namespace std;
#define Fopen freopen("_in.txt","r",stdin); freopen("_out.txt","w",stdout);
#define LL long long
#define ULL unsigned LL
#define fi first
#define se second
#define pb push_back
#define lson l,m,rt<<1
#define rson m+1,r,rt<<1|1
#define lch(x) tr[x].son[0]
#define rch(x) tr[x].son[1]
#define max3(a,b,c) max(a,max(b,c))
#define min3(a,b,c) min(a,min(b,c))
typedef pair<int,int> pll;
const int inf = 0x3f3f3f3f;
const int _inf = 0xc0c0c0c0;
const LL INF = 0x3f3f3f3f3f3f3f3f;
const LL _INF = 0xc0c0c0c0c0c0c0c0;
const LL mod = (int)1e9+;
const int N = 1e5 + ;
char s[N][];
int sum[N];
int ans[N];
long double f[N];
struct Node{
int j, l, r;
}q[N];
int n, l, p;
LL maxxx = 1e18;
long double val(int i, int j){
if(i > j) swap(i,j);
long double tt = abs(sum[j]-sum[i]+j-i--l);
long double zz = ;
for(int i = ; i <= p; ++i){
zz *= tt;
}
zz += f[i];
return zz;
}
void solve(int n){
if(n == ) return ;
solve(ans[n]);
for(int i = ans[n]+; i <= n; ++i){
printf("%s%c",s[i]," \n"[i==n]);
}
}
int main(){
// cout << (702871197447575ll<1e18) << endl;
int T;
scanf("%d", &T);
for(int _ = ; _ <= T; ++_){
scanf("%d%d%d", &n, &l, &p);
for(int i = ; i <= n; ++i){
scanf("%s", s[i]);
sum[i] = sum[i-] + strlen(s[i]);
}
int L = , R = ;
q[L] = {,,n};
int midl;
for(int i = ; i <= n; ++i){
q[L].l = i;
while(L <= R && q[L].r < i) ++L;
ans[i] = q[L].j;
f[i] = val(q[L].j,i);
midl = n+;
while(L <= R && val(q[R].j, q[R].l) >= val(i, q[R].l)){
R--;
}
if(L <= R){
int ll = q[R].l, rr = q[R].r;
while(ll <= rr){
int mid = (ll+rr) >> ;
if(val(q[R].j,mid) < val(i, mid)) ll = mid+;
else rr = mid - ;
}
if(ll <= n){
q[R].r = ll-;
q[++R] = {i,ll,n};
}
}
else {
q[++R] = {i,i+,n};
}
}
if(f[n] > maxxx)
puts("Too hard to arrange");
else{
LL fans = f[n];
printf("%lld\n", fans);
solve(n);
}
puts("--------------------");
}
return ;
}