BZOJ1563: [NOI2009]诗人小G(决策单调性 前缀和 dp)

题意

题目链接

sol

很显然的一个dp方程

\(f_i = min(f_j + (sum_i - sum_j - 1 - l)^p)\)

其中\(sum_i = \sum_{j = 1}^i len_j + 1\)

这个东西显然是有决策单调性的。

单调队列优化一下

我好像已经做过三个这种类型的题了，而且转移的时候\(w\)中总是带个幂函数。。interesting

#include<bits/stdc++.h>
#define chmax(a, b) (a = (a > b ? a : b))
#define chmin(a, b) (a = (a < b ? a : b))
#define ll long long
#define ldb long double 
//#define int long long 
using namespace std;
const int maxn = 1e5 + 10;
inline int read() {
    int x = 0, f = 1; char c = getchar();
    while(c < '0' || c > '9') {if(c == '-') f = -1; c = getchar();}
    while(c >= '0' && c <= '9') x = x * 10 + c - '0', c = getchar();
    return x * f;
}
int t, n, l, p, sum[maxn], q[maxn], c[maxn], pre[maxn];//c???ߵ?λ?
char str[maxn][35];
ldb f[maxn];
ldb fastpow(ldb a, int p) {
    ldb base = 1;
    while(p) {
        if(p & 1) base = base * a; 
        a = a * a; p >>= 1;
    }
    return base;
}
ldb calc(int j, int i) {
    return f[j] + fastpow(abs(sum[i] - sum[j] - l), p);
}
int lower(int x, int y) {//???x????????
    int l = x, r = n + 1, ans = 0;
    while(l <= r) {
        int mid = l + r >> 1;
        if(calc(x, mid) >= calc(y, mid)) r = mid - 1;
        else l = mid + 1;
    }
    return l;
}
void solve() {
    n = read(); l = read() + 1; p = read();
    for(int i = 1; i <= n; i++) {
        scanf("%s", str[i] + 1);
        sum[i] = sum[i - 1] + strlen(str[i] + 1) + 1;
    }
    memset(q, 0, sizeof(q));
    for(int i = 1, h = 2, t = 2; i <= n; i++) {
        while(h < t && c[h] <= i) h++;
        f[i] = calc(q[h], i); pre[i] = q[h];
        while(h < t && c[t - 1] >= lower(q[t], i)) t--;
        c[t] = lower(q[t], i); q[++t] = i;
    }
    if(f[n] > 1e18) {puts("too hard to arrange\n--------------------"); return;}
    printf("%.0lf\n", f[n]);
    puts("--------------------");
}
main() {
    for(t = read(); t; t--) solve();
}