zkx06111's Blog

BZOJ 1563 诗人小G

| Comments

dp方程很显然:令表示以第句话结尾的最小不协调度,则有

状态数是的,转移是的,所以复杂度是的,无法通过所有数据。

但是这题满足决策单调性(证明待补):设的决策,对于。也就是说,对于一个决策,以它为最优决策的位置一定是连续的一段,对于最优决策,如果它们之间没有其他的最优决策,那么它们对应的两个区间是相邻的。可以据此进行优化,步骤如下:

1.显然k(1) = 0,那么当前[1, n]的最优决策是1,更新F[1]的值,把决策(l = 1, r = n, x = 1)加入栈中。

2.从2到n枚举决策,当一个决策i被枚举到的时候,它所在位置的F值已经在前面被更新过了,之后再也不会被更新了。查看当前的决策会不会在栈顶决策对应区间的某个子区间上比栈顶决策要优,如果整个区间上都比它优(栈顶决策的左端点比它优)就弹栈,找到那个分界点m,使得m - 1的位置当前栈顶优,m的位置i优,修改栈顶决策的右端点为m - 1,并把决策(l = m, r = n, x = i)加入栈中。

看代码可能更清楚。

#include <bits/stdc++.h>
#define REP(i, a, b) for (int i = a; i <= b; ++i)
#define PER(i, a, b) for (int i = a; i >= b; --i)
#define RVC(i, S) for (int i = 0; i < S.size(); ++i)
#define pb push_back
#define mp make_pair
#define fi first
#define se second
#define debug(...) fprintf(stderr, __VA_ARGS__)
using namespace std;
 
typedef long long LL;
typedef vector<int> VI;
typedef pair<int, int> pii;
typedef long double ld;
 
inline int read(){
    int x = 0, ch = getchar(), f = 1;
    while (!isdigit(ch)){if (ch == '-') f = -1; ch = getchar();}
    while (isdigit(ch)) x = x * 10 + ch - '0', ch = getchar();
    return x * f;
}

const int N = 100005;
int n, L, P, tp, sum[N];
char str[35];
ld fd[N];

struct choice{
    int x, l, r;
} st[N];

inline ld pwr(ld a, int b){
    ld res = 1;
    REP(i, 1, b) res *= a;
    return res;
}

inline ld solve(int i, int j){
    return fd[j] + pwr(abs(sum[i] - sum[j] + i - j - 1 - L), P);
}

int main(){
    int kas = read();
    while (kas--){
        n = read(), L = read(), P = read();
        REP(i, 1, n){
            scanf("%s", str);
            sum[i] = sum[i - 1] + strlen(str);
        }

        st[tp = 1] = (choice){0, 1, n};
        fd[1] = solve(1, 0);
        
        REP(i, 1, n - 1){
            choice c = st[tp];
            while (c.l > i && solve(c.l, c.x) > solve(c.l, i)){
                --tp; c = st[tp];
            }
            int l = max(c.l, i + 1), r = n + 1, res = -1;
            while (l <= r){
                int mid = l + r >> 1;
                if (solve(mid, c.x) >= solve(mid, i)){
                    res = mid; r = mid - 1;
                }
                else l = mid + 1;
            }
            if (res != -1){
                --tp; c.r = res - 1;
                st[++tp] = c;
                st[++tp] = (choice){i, res, n};
            }
            l = 1, r = tp, res = -1;
            while (l <= r){
                int mid = l + r >> 1;
                if (st[mid].l <= i + 1 && i + 1 <= st[mid].r){
                    res = mid; break;
                }
                if (st[mid].r < i + 1) l = mid + 1;
                else r = mid - 1;
            }
            fd[i + 1] = solve(i + 1, st[res].x);
            //debug("f[%d] = %lld\n", i + 1, (LL)fd[i + 1]);
     }
        if (fd[n] > 1e18)
            printf("Too hard to arrange\n");
        else printf("%lld\n", (LL)(fd[n] + 0.5));
        printf("--------------------\n");
    }
    return 0;
}

Comments

comments powered by Disqus