[BZOJ1563][NOI2009]诗人小G（DP+四边形不等式优化）

Address

https://www.lydsy.com/JudgeOnline/problem.php?id=1563

Solution

令 S$S$ 为句子长度的前缀和， f[i]$f[i]$ 为前 i$i$ 个句子的最小不和谐度。

f[i]=minj=0i−1{f[j]+|Si−Sj|P}$$f[i]=\underset{j=0}{\overset{i-1}{min}}\{f[j]+|S_i-S_j{|}^P\}$$

通过证 (gui) 明 (lv) ，我们得到：

|Si−Sj|P+|Si+1−Sj+1|P≤|Si+1−Sj|P+|Si−Sj+1|P$$|S_i-S_j{|}^P+|S_{i+1}-S_{j+1}{|}^P\le |S_{i+1}-S_j{|}^P+|S_i-S_{j+1}{|}^P$$

故 f$f$ 满足决策单调性。
用一个栈记录决策表。
栈的每个元素是一个三元组 (l,r,x)$(l,r,x)$ 表示当前 f[l...r]$f[l...r]$ 的最优决策为 x$x$ （三个元素都递增）。
一开始栈中有一个元素 (1,n,0)$(1,n,0)$ 。
考虑求出一个 f[i]$f[i]$ 时如何用 f[i]$f[i]$ 更新部分决策。
（1）对于栈顶 (l,r,x)$(l,r,x)$ ，如果 f[l]+|Sl−Si|P<f[l]+|Sl−Sx|P$f[l]+|S_l-S_i{|}^P<f[l]+|S_l-S_x{|}^P$ ，那么 f[l]$f[l]$ 取决策 i$i$ 比 x$x$ 优，可退栈，然后继续执行（1），直到 l≤i$l\le i$ 或者 上式不满足为止。
（2）否则在 [max(l,i+1),r]$[max(l,i+1),r]$ 内找到一个点 k$k$ ，使得 f[k−1]$f[k-1]$ 取决策 x$x$ 比 i$i$ 优， f[k]$f[k]$ 取决策 i$i$ 比 x$x$ 优。这时候将栈顶的 r$r$ 改成 k−1$k-1$ ，将三元组 (k,n)$(k,n)$ 入栈（当然，如果 k>n$k>n$ 就不要入栈）。可以用二分查找找到这样的 k$k$ 。
复杂度 O(Tnlogn)$O(Tn\log n)$ 。
注意 f$f$ 会超过 long long 范围，要使用 long double 。

Code

#include <cmath>
#include <cstdio>
#include <cstring>
#include <iostream>
#include <algorithm>
#define For(i, a, b) for (i = a; i <= b; i++)
#define Rof(i, a, b) for (i = a; i >= b; i--)
using namespace std;
typedef long double ld;
const int N = 1e5 + 5, E = 33;
int n, l, p, top, sum[N];
char s[N][E];
ld f[N];
struct cyx {
    int l, r, x;
} stk[N];
ld w(int j, int i) {
    ld res = 1, a = abs(sum[i] - sum[j] + i - j - 1 - l);
    int b = p;
    while (b) {
        if (b & 1) res = res * a;
        a = a * a;
        b >>= 1;
    }
    return res;
}
void work() {
    int i, j, k, th = 1;
    scanf("%d%d%d", &n, &l, &p);
    For (i, 1, n) scanf("%s", s[i] + 1),
        sum[i] = sum[i - 1] + strlen(s[i] + 1);
    stk[top = 1] = (cyx) {1, n, 0};
    For (i, 1, n) {
        f[i] = f[stk[th].x] + w(stk[th].x, i);
        while (stk[top].l > i && f[i] + w(i, stk[top].l) <
            f[stk[top].x] + w(stk[top].x, stk[top].l)) top--;
        int L = max(stk[top].l, i + 1), R = stk[top].r;
        while (L <= R) {
            int mid = L + R >> 1;
            if (f[i] + w(i, mid) < f[stk[top].x]
                + w(stk[top].x, mid)) R = mid - 1;
            else L = mid + 1;
        }
        stk[top].r = L - 1;
        if (L <= n) stk[++top] = (cyx) {L, n, i};
        if (stk[th].r == i) th++;
    }
    if (f[n] > 1e18) puts("Too hard to arrange");
    else printf("%lld\n", (long long) (f[n] + 0.5));
    puts("--------------------");
}
int main() {
    int T; cin >> T;
    while (T--) work();
    return 0;
}