变成 10pts 了，其他全 WA
救救孩子吧
```cpp
#include <algorithm>
#include <deque>
#include <iostream>
#include <string>
using std::cin;
using std::cout;
using std::string;
using i32 = int;
using i64 = long long;
using i128 = __int128;
using f128 = long double;
#define N 100005
template <typename T>
T abs(const T& x) {
return x < 0 ? -x : x;
}
const i64 inf = 0x3f3f3f3f3f3f3f3f;
i32 t;
string poem[N];
i32 pre[N]; // 最佳决策点
f128 f[N];
i64 s[N];
i32 n, p;
i64 l;
struct d {
i32 l, r, p;
};
f128 calc(const i32& i, const i32& j) {
f128 res = 1;
i32 p = ::p;
for (f128 a = abs(s[i] - s[j] - 1 - l); p; p >>= 1, a = a * a) // ::p 就是把全局变量 p 复制进来，但是不修改全局的 p
if (p & 1) {
res *= a;
} // 快速幂，log(10)=3，算常数复杂度
return res + f[j];
}
i32 find(const d& x, const i32& i) {
i32 l = x.l, r = x.r;
while (l < r) {
i32 mid = (l + r) >> 1;
if (calc(mid, x.p) >= calc(mid, i))
r = mid;
else
l = mid + 1;
}
return l;
}
void output(i32 x) {
if (pre[x]) output(pre[x]);
for (i32 i = pre[x] + 1; i <= x; ++i) {
cout << poem[i];
if (i != x) cout << ' ';
}
if (x != n) cout << '\n';
}
void solve() {
cin >> n >> l >> p;
for (i32 i = 1; i <= n; ++i) {
cin >> poem[i];
s[i] = poem[i].size() + s[i - 1] + 1;
}
// DP 部分
std::deque<d> q;
q.emplace_front((d){ 1, n, 0 }); // 第一个可决策点就是 0
for (i32 i = 1; i <= n; ++i) {
if (!q.empty()) {
if (q.front().r == i - 1)
q.pop_front();
else
q.front().l = i; // 没用的决策扔掉
}
i32 j = q.front().p;
f[i] = calc(i, j);
pre[i] = j; // 记录最佳决策点
// 插入新决策
i32 pos = q.back().l;
// 情况一：当前决策点比队尾优
while (!q.empty() && calc(q.back().l, q.back().p) >= calc(q.back().l, i)) {
pos = q.back().l;
q.pop_back();
}
// 情况二：当前决策点可能部分优于队尾
if (!q.empty()) {
if (calc(q.back().r, q.back().p) <= calc(q.back().r, i)) // i 不优于 队尾
q.emplace_back((d){ pos, n, i });
else {
pos = find(q.back(), i);
q.back().r = pos - 1;
q.emplace_back((d){ pos, n, i });
}
} else
q.emplace_back((d){ pos, n, i });
}
if (f[n] > 1e18) goto failed;
cout << (i64)f[n] << std::endl;
output(n);
cout.put('\n');
return;
failed:
cout << "Too hard to arrange\n";
}
int main() {
std::ios::sync_with_stdio(false);
cin.tie(nullptr);
cout.tie(nullptr);
cin >> t;
while (t--) {
solve();
cout << "--------------------";
if (t) cout.put('\n');
}
return 0;
}
```
by Tibrella @ 2023-07-12 22:30:54
过了。
更新决策之前判断一下是否有效，即这个决策的 $l\leqslant n$ 才算有效
```cpp
if (pos <= n) {
q.back().r = pos - 1;
q.emplace_back((d){ pos, n, i });
}
```
感谢 Utsuji_risshū 的题解，跟我的实现思路基本一样
by Tibrella @ 2023-07-13 09:06:16
话不多说，直接上代码！！
```
#include<bits/stdc++.h>
#define ffor(i,a,b) for(int i=(a);i<=(b);i++)
#define roff(i,a,b) for(int i=(a);i>=(b);i--)
using namespace std;
const int MAXN=1e5+10;
int T,n,l,p,len[MAXN],pre[MAXN]; char S[MAXN][32]; long double dp[MAXN];
#define fi first
#define se second
int h,t; pair<pair<int,int>,int> ar[MAXN];
long double pows(long double k,int v) {
long double res=1;
while(v) {
if(v&1) res*=k;
k*=k,v>>=1;
}
return res;
}
long double omega(int lst,int pos) {
return dp[lst]+pows(abs((long double)(len[pos]-len[lst]+pos-lst-1-l)),p);
}
int bfind(int i,int lst,int l,int r) {
int ans=0;
while(l<=r) {
int mid=l+r>>1;
if(omega(lst,mid)<=omega(i,mid)) ans=mid,l=mid+1; else r=mid-1;
}
return ans;
}
void output(int k) {
if(k==0) return ;
output(pre[k]);
ffor(i,pre[k]+1,k-1) printf("%s ",S[i]); printf("%s\n",S[k]);
}
void work(void) {
scanf("%d %d %d",&n,&l,&p);
ffor(i,1,n) scanf("%s",S[i]),len[i]=strlen(S[i])+len[i-1];
h=1,t=0;
ar[++t]={{1,n},0};
ffor(i,1,n) {
while(ar[h].fi.se<i) h++;
dp[i]=omega(ar[h].se,i),pre[i]=ar[h].se;
ar[h].fi.fi=i+1; if(ar[h].fi.fi>ar[h].fi.se) h++;
int L=-1;
while(h<=t) {
int lst=ar[t].se,l=ar[t].fi.fi,r=ar[t].fi.se;
if(omega(i,l)<=omega(lst,l)) {L=l,t--;continue;}
if(omega(i,r)>=omega(lst,r)) {L=r+1;break;}
L=bfind(i,lst,l,r-1)+1; ar[t].fi.se=L-1; break;
}
if(L<=n) ar[++t]={{L,n},i};
}
if(dp[n]>1e18) printf("Too hard to arrange\n");
else {
printf("%lld\n",(long long)(dp[n]+0.5));
output(n);
}
printf("--------------------\n");
}
int main() {
cin>>T; while(T--) work();
return 0;
}
```
求关！！！
by Zjg15269187511 @ 2023-07-15 21:23:37