题解
决策单调性优化的一道题。
对于一个转移 (f[i,j] = min{ f[i][k] + f[k + 1][j] + w(i,j) })， 如果(w(i,j))满足四边形不等式和区间包含单调，那么(f[i,j])也满足四边形不等式和区间包含单调。而四边形不等式就意味着最优决策点是单调的。这个证明可在很多论文中找到。
而这题的特殊之处在于，对于转移 (f[i] = min{f[j] + w(j,i)}), 只需要(w)满足四边形不等式，(f)就满足决策单调。
给出证明：
设 $ x $ 的最优决策点为 (i), (x + 1) 的最优决策点为 (j)。如果结论不成立，那么有(j<i<x<x+1)
根据四边形不等式，我们已经知道(w(j,x+1)+w(i,x) >= w(i,x+1) + w(j,x))
因为 (j) 不是 (x) 的最优决策点， $ i $ 不是 $ x + 1 $ 的最优决策点，因此有：
$ f[j] + w(j,x) >= f[x] ( ) f[i] + w(i,x + 1) >= f[x + 1] $
两式相加，我们就得到 :
$ w(j,x) + w(i, x + 1) >= (f[x] - f[i]) + (f[x + 1] - f[j]) = w(i, x) + w(j, x + 1) $
这就和四边形不等式矛盾了。
这道题里面，(f[i] = min{f[j] + w(j, i)})， 其中(w(j,i))等于([j+1,i])长度产生的代价。
分讨求导一下就可以得到(w(j,i))满足四边形不等式，由上得出(f)满足决策单调。
维护一个决策点的单调队列，记下每个决策点比前一个决策点优的时间。这个时间可以在加入队列的时候二分得到。需要注意的是如果加入一个新元素时，它比队尾优的时间早于队尾比前一个决策点优的时间，那么队尾就应该被弹出。
这题爆(long long)非常麻烦，(long double)可以水过去。
#include<bits/stdc++.h>
#define fi first
#define se second
#define LL long long
#define LD long double
#define pii pair<int, int>
using namespace std;
const int N = 1e5 + 10;
const LL LIMIT = 1e18;
template<typename T> void read(T &x) {
char c = getchar(); int f = 0;
while (c < '0' || c > '9') f |= (c == '-'), c = getchar();
for (x = 0; c >= '0' && c <= '9'; c = getchar())
x = (x << 3) + (x << 1) + (c ^ '0');
if (f) x = -x;
}
LL n, L, p;
LL a[N], pre[N];
LD f[N], sum[N];
char s[N][35];
int h, t;
pii q[N];
LD Qpow(LD x, int p) {
LD ans = 1;
while (p) {
if (p & 1) ans = ans * x;
x = x * x;
p >>= 1;
}
return ans;
}
LD w(int x, int y) {
return Qpow(abs(sum[y] - sum[x] + y - x - 1 - L), p);
}
void solve() {
read(n); read(L); read(p);
for (int i = 1; i <= n; ++i) {
scanf("%s", s[i] + 1);
a[i] = strlen(s[i] + 1);
sum[i] = sum[i - 1] + a[i];
}
f[0] = 0;
h = 1, t = 0;
q[++t] = make_pair(0, 1);
for (int i = 1; i <= n; ++i) {
while (t - h >= 1 && q[h + 1].se <= i) ++h;
int x = q[h].fi;
pre[i] = x;
f[i] = f[x] + w(x, i);
while (h <= t) {
int y = q[t].fi;
LD s1 = f[y] + w(y, max(i + 1, q[t].se));
LD s2 = f[i] + w(i, max(i + 1, q[t].se));
if (s2 <= s1) --t;
else break;
}
if (h > t) q[++t] = make_pair(i, i + 1);
else {
int x = q[t].fi;
int L = max(i, q[t].se) + 1, R = n, ans = n + 1;
while (L <= R) {
int mid = (L + R) >> 1;
LD s1 = f[x] + w(x, mid);
LD s2 = f[i] + w(i, mid);
if (s2 <= s1) {
R = mid - 1;
ans = mid;
}
else L = mid + 1;
}
if (ans <= n) q[++t] = make_pair(i, ans);
}
}
if (f[n] > LIMIT) {
puts("Too hard to arrange");
}
else {
cout << (LL)f[n] << endl;
stack<int> st;
int now = n;
while (now) {
st.push(now);
now = pre[now];
}
int las = 0;
while (!st.empty()) {
int x = st.top(); st.pop();
for (int i = las + 1; i < x; ++i) {
printf("%s ", s[i] + 1);
}
printf("%s
", s[x] + 1);
las = x;
}
}
puts("--------------------");
}
int main() {
int T; read(T);
while (T--) solve();
return 0;
}