BZOJ 1563
题意：有一个长度为 $n$ 的序列 $A$ 和常数 $L,P$ ，你需要将它分成若干段，每一段的代价为 $|\sum A_i−L|^P$ ，求最小代价的划分方案。
易得暴力DP
$$
dp(i) = \min_{j = 0} ^ {i - 1} (|\text{sum}(i) - \text{sum}(j) - L|^P + dp(j))
$$
发现这个$dp$满足决策单调性，即如果我们把每个位置$i$由哪个位置转移而来记为$g(i)$，则$g(i)$为单调不减的
这个可以数学证明也可以打表验证
然后我们就可以通过一个队列来完成优化，即我们队列存的是三元组$(l,r,j)$表示$[l,r]$区间的$dp$值的最优决策为$j$
那么我们每次在队头删掉$r$小于当前枚举的$i$的三元组
然后就就可以取队头元素来计数$dp(i)$
然后我们在队尾处理，如果当前有决策$i$, 队尾三元组$(l_t,r_t,j_t)$，则如果$\text{val}(i, l_t) \leq \text{val}(l_j, l_t)$，那么删掉队尾三元组
然后我们尝试插入当前的$i$，我们在当前$[l_t,r_t]$中二分一个位置$pos$，使得$j_t$是$[l_t,pos-1]$的最优决策，$i$是$[pos, r_t]$的最优决策
最后注意开 long double 来判断是否大于$10^{18}$
#include<cstdio>
#include<cstring>
#include<algorithm>
#include<iostream>
#include<cmath>
#include<map>
#include<queue>
#include<string>
#define ms(i, j) memset(i, j, sizeof i)
#define LL long double
#define db double
#define fir first
#define sec second
#define mp make_pair
using namespace std;
namespace flyinthesky {
struct node {int l, r, j;} q[100000 + 5];
int n, L, P, fr[100000 + 5], l, r, stk[100000 + 5], top;
LL dp[100000 + 5], sum[100000 + 5];
char s[100000 + 5][35];
LL calc(int j, int i) {
LL gg = sum[i] - sum[j] - L + i - j - 1, ret = 1;
if (gg < 0) gg = -gg;
for (int i = 1; i <= P; ++i) ret *= gg;
return dp[j] + ret;
}
int find(node a, int y) {
int l = a.l, r = a.r;
while (l <= r) {
int mid = (l + r) >> 1;
if (calc(a.j, mid) < calc(y, mid)) l = mid + 1; else r = mid - 1;
}
return l;
}
void clean() {
}
int solve() {
clean();
cin >> n >> L >> P;
for (int i = 1; i <= n; ++i) scanf("%s", s[i]), sum[i] = sum[i - 1] + strlen(s[i]);
q[l = r = 1] = (node){1, n, 0};
for (int i = 1; i <= n; ++i) {
while (l < r && q[l].r < i) ++l;
dp[i] = calc(q[l].j, i), fr[i] = q[l].j;
while (l <= r && calc(i, q[r].l) <= calc(q[r].j, q[r].l)) --r;
if (l > r) q[++r] = (node){i, n, i};
else if (calc(i, n) <= calc(q[r].j, n)) { // 二分找得到这样的 pos 吗?
int pos = find(q[r], i);
q[r].r = pos - 1, q[++r] = (node){pos, n, i};
}
}
if (dp[n] > 1e18) puts("Too hard to arrange");
else {
printf("%lld\n", (long long)dp[n]);
int now = n;
top = 0;
while (now) stk[++top] = now, now = fr[now];
for (int lst = 0, i = top; i; --i) {
for (int j = lst + 1; j <= stk[i]; ++j) printf("%s%c", s[j], j == stk[i] ? '\n' : ' ');
lst = stk[i];
}
}
puts("--------------------");
return 0;
}
}
int main() {
int T; cin >> T;
while (T--) flyinthesky::solve();
return 0;
}
/*
*/
