[NOI2009]诗人小G

题解

决策单调性优化的一道题。

对于一个转移 \(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\n", s[x] + 1);
            las = x;
        }
    }
    puts("--------------------");
}

int main() {
    int T; read(T);
    while (T--) solve();
    return 0;
}

[NOI2009]诗人小G

原文：https://www.cnblogs.com/Vexoben/p/11728785.html