[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]=minj=0i−1{f[j]+|Si−Sj|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 ≤ | 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 比 xx 優，可退棧，然後繼續執行（1），直到 l≤i l ≤ i 或者 上式不滿足為止。

（2）否則在 [max(l,i+1),r] [ max ( l , i + 1 ) , r ] 内找到一個點 k k ，使得 f[k−1]f[k−1] 取決策 x x 比 ii 優， f[k] f [ k ] 取決策 i i 比 xx 優。這時候将棧頂的 r r 改成 k−1k−1 ，将三元組 (k,n) ( k , n ) 入棧（當然，如果 k>n k > n 就不要入棧）。可以用二分查找找到這樣的 k k 。

複雜度 O(Tnlogn)O(Tnlog⁡n) 。

注意 f f <script type="math/tex" id="MathJax-Element-2332">f</script> 會超過 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 =  + , E = ;
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 = , a = abs(sum[i] - sum[j] + i - j -  - l);
    int b = p;
    while (b) {
        if (b & ) res = res * a;
        a = a * a;
        b >>= ;
    }
    return res;
}
void work() {
    int i, j, k, th = ;
    scanf("%d%d%d", &n, &l, &p);
    For (i, , n) scanf("%s", s[i] + ),
        sum[i] = sum[i - ] + strlen(s[i] + );
    stk[top = ] = (cyx) {, n, };
    For (i, , 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 + ), R = stk[top].r;
        while (L <= R) {
            int mid = L + R >> ;
            if (f[i] + w(i, mid) < f[stk[top].x]
                + w(stk[top].x, mid)) R = mid - ;
            else L = mid + ;
        }
        stk[top].r = L - ;
        if (L <= n) stk[++top] = (cyx) {L, n, i};
        if (stk[th].r == i) th++;
    }
    if (f[n] > ) puts("Too hard to arrange");
    else printf("%lld\n", (long long) (f[n] + ));
    puts("--------------------");
}
int main() {
    int T; cin >> T;
    while (T--) work();
    return ;
}