题意

有一个长度为 \(n\) 的序列 \(A\) 和常数 \(L, P\) ，你需要将它分成若干段，每 \(P\) 一段的代价为 \(| \sum ( A_i ) − L|^P\) ，求最小代价的划分方案。

\(n \le 10^5 , 1 \le P \le 10\)

题解

考虑暴力 \(O(n^2)\) dp。

\[dp_i = \min_{j = 0} ^ {i - 1} |sum_j - sum_i - L|^P + dp_j
\]

这个方程是具有决策单调性的。

决策单调性是指，对于任意 \(u < v < i < j\) ，若在 \(i\) 处决策 \(v\) 优于决策 \(u\) ，则在 \(j\) 处必有决策 \(v\) 优于决策 \(u\) 。

至于证明，你考虑那是个二次函数，一阶导数单增等性质就可以了。

然后考虑用一个栈来维护每个决策会更新的区间就行了，新加入一个决策时要二分得到它的区间。

令 \(f(i, j)\) 为从 \(i\) 转移到 \(j\) 得到的 \(dp_j\) 。

具体二分的时候就找到 \(f(i, mid) - f(stk[top], mid)\) 的零点就行了，之后的点肯定 \(i\) 更优。

然后每次转移的话就二分找到当前这个点属于的决策区间，注意边界问题，然后每次要把栈顶所有当前不优于它的状态都要弹掉。

所以最后复杂度就是 \(O(n \log n)\) 的。

总结

决策单调性优化都可以用栈维护转移区间，然后每次二分找转移点，以及求区间就行了。

代码

#include <bits/stdc++.h>

#define For(i, l, r) for(register int i = (l), i##end = (int)(r); i <= i##end; ++i)

#define Fordown(i, r, l) for(register int i = (r), i##end = (int)(l); i >= i##end; --i)

#define Set(a, v) memset(a, v, sizeof(a))

#define Cpy(a, b) memcpy(a, b, sizeof(a))

#define debug(x) cout << #x << ": " << (x) << endl

#define DEBUG(...) fprintf(stderr, __VA_ARGS__)

using namespace std;

typedef long double ld;

typedef long long ll;

template<typename T> inline bool chkmin(T &a, T b) {return b < a ? a = b, 1 : 0;}

template<typename T> inline bool chkmax(T &a, T b) {return b > a ? a = b, 1 : 0;}

inline int read() {

    int x(0), sgn(1); char ch(getchar());

    for (; !isdigit(ch); ch = getchar()) if (ch == '-') sgn = -1;

    for (; isdigit(ch); ch = getchar()) x = (x * 10) + (ch ^ 48);

    return x * sgn;

}

void File() {

#ifdef zjp_shadow

    freopen ("P1912.in", "r", stdin);

    freopen ("P1912.out", "w", stdout);

#endif

}

const int N = 1e5 + 1e3;

int n, Pow, L;

int sum[N], pre[N], stk[N], seg[N];

int ans[N]; char str[N][50];

ld dp[N];

ld fpm(ld x, int power) {

    ld res = 1;

    for (; power; power >>= 1, x *= x)

        if (power & 1) res *= x;

    return res;

}

ld Calc(int S, int T) {

    return S >= T ? 1e18 + 1 : dp[S] + fpm(abs(sum[T] - sum[S] - L), Pow);

}

int main () {

    File();

    int cases = read();

    while (cases --) {

        n = read(); L = read(); Pow = read();

        For (i, 1, n) {

            scanf ("%s", str[i]);

            sum[i] = sum[i - 1] + strlen(str[i]) + 1;

        }

        ++ L;

        int top = 1; stk[1] = seg[1] = dp[0] = 0;

        For (i, 1, n) {

            int pos = upper_bound(seg + 1, seg + top + 1, i) - seg - 1;

            dp[i] = Calc(pre[i] = stk[pos], i);

            for (; top && Calc(stk[top], seg[top]) > Calc(i, seg[top]); -- top);

            int l = seg[top], r = n, res = 0;

            while (l <= r) {

                int mid = (l + r) >> 1;

                if (Calc(stk[top], mid) <= Calc(i, mid))

                    res = mid, l = mid + 1;

                else

                    r = mid - 1;

            }

            if (res < n)

                seg[++ top] = res + 1, stk[top] = i;

        }

        if (dp[n] > 1e18) puts("Too hard to arrange");

        else {

            printf ("%lld\n", (ll) dp[n]);

            top = 0;

            for (int u = n; u; u = pre[u])

                ans[++ top] = u;

            ans[top + 1] = 0;

            Fordown (i, top, 1) For(j, ans[i + 1] + 1, ans[i])

                printf ("%s%c", str[j], j == jend ? '\n' : ' ');

        }

        puts("--------------------");

    }

    return 0;

}

巴特西

[NOI2009]诗人小G（dp + 决策单调性优化）

题意

题解

总结

代码

最新文章

热门文章