【BZOJ1563】【NOI2009】詩人小G（DP，決策單調性）

Description

https://www.luogu.org/problemnew/show/P1912

Solution

設 dpi d p i 表示到第 i i 句詩的最小不協排程，那麼顯然有：

dpi=minj=1i−1dpj+|l−sumi+sumj−i+j+1|pdpi=minj=1i−1dpj+|l−sumi+sumj−i+j+1|p

這是一個具有決策單調性的1D/1D動态規劃，我們每處理完一個 dpi d p i ，就二分其決策區間，舉個栗子：

一開始序列的決策點為：

0000000000

。

得到 dp1 d p 1 後，決策點變成了：

0011111111

。

得到 dp2 d p 2 後變成了醬紫：

0011122222

。

得到 dp3 d p 3 後，有可能是：

0011122233

，也有可能是

0013333333

。

我們二分得到決策區間的分界線、用棧來維護即可。

Code

/************************************************
 * Au: Hany01
 * Date: Aug 5th, 2018
 * Prob: BZOJ1563 詩人小G
 * Email: [email protected]
 * Inst: Yali High School
************************************************/

#include<bits/stdc++.h>

using namespace std;

typedef long long LL;
typedef long double LD;
typedef pair<int, int> PII;
#define rep(i, j) for (register int i = 0, i##_end_ = (j); i < i##_end_; ++ i)
#define For(i, j, k) for (register int i = (j), i##_end_ = (k); i <= i##_end_; ++ i)
#define Fordown(i, j, k) for (register int i = (j), i##_end_ = (k); i >= i##_end_; -- i)
#define Set(a, b) memset(a, b, sizeof(a))
#define Cpy(a, b) memcpy(a, b, sizeof(a))
#define x first
#define y second
#define pb(a) push_back(a)
#define mp(a, b) make_pair(a, b)
#define SZ(a) ((int)(a).size())
#define INF (0x3f3f3f3f)
#define INF1 (2139062143)
#define debug(...) fprintf(stderr, __VA_ARGS__)
#define y1 wozenmezhemecaia

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

inline int read() {
    static int _, __; static char c_;
    for (_ = , __ = , c_ = getchar(); c_ < '0' || c_ > '9'; c_ = getchar()) if (c_ == '-') __ = -;
    for ( ; c_ >= '0' && c_ <= '9'; c_ = getchar()) _ = (_ << ) + (_ << ) + (c_ ^ );
    return _ * __;
}

const int maxn =  + ;

LD dp[maxn];
int n, l, p, sum[maxn], pre[maxn], top, nxt[maxn];
PII stk[maxn];
char str[maxn][];

inline LD Pow(LD a, int b) {
    static LD Ans;
    for (Ans = ; b; b >>= , a *= a) if (b & ) Ans *= a;
    return Ans;
}

inline LD calc(int i, int j) { return dp[j] + Pow((LD)abs(l - sum[i] + sum[j] - i + j + ), p); }

int main()
{
#ifdef hany01
    freopen("bzoj1563.in", "r", stdin), freopen("bzoj1563.out", "w", stdout);
#endif

    for (static int Cas = read(), pos; Cas --; ) {
        n = read(), l = read(), p = read();
        For(i, , n) scanf("%s", str[i]), sum[i] = sum[i - ] + strlen(str[i]), dp[i] = ;
        stk[top = ] = mp(, );
        For(i, , n) {
            dp[i] = calc(i, pos = stk[upper_bound(stk + , stk +  + top, mp(i, INF)) - stk - ].y);
            pre[i] = pos;
            if (calc(n, i) <= calc(n, stk[top].y)) {
                stk[++ top] = mp(n, i);
                for (register int l, r, mid; ; ) {
                    l = max(stk[top - ].x, i + ), r = n;
                    while (l < r) {
                        mid = (l + r) >> ;
                        if (calc(mid, stk[top - ].y) >= calc(mid, i)) r = mid; else l = mid + ;
                    }
                    stk[top].x = l;
                    if (stk[top].x > stk[top - ].x) break;
                    stk[top - ] = stk[top], -- top;
                }
            }
        }
        if (dp[n] >  + ) puts("Too hard to arrange");
        else {
            printf("%lld\n", (LL)dp[n]);
            for (int t = n; t; t = pre[t]) nxt[pre[t]] = t;
            for (int t = ; t < n; t = nxt[t])
                For(i, t + , nxt[t]) printf("%s%c", str[i], i == nxt[t] ? '\n' : ' ');
        }
        puts("--------------------");
    }

    return ;
}