诗人小 G

啊。。我觉得这个还是挺难的。。。

#include <lastweapon/io>
using namespace lastweapon;

const int N = int(1e5) + 9;
long double f[N]; int pre[N];
char str[N][31]; int s[N];
PII Q[N]; int cz, op;
int n,l,p;

long double poww(long double x, int b) {
    long double z = 1;
    while (b) {
        if (b&1) z *= x;
        x *= x; b >>= 1;
    }
    return z;
}


long double calc(int a, int b) {
    return f[a] + poww(abs(s[b]-s[a]-l), p);
}

int left(int a, int b) {
    int l = a, r = n+1;
    while (l < r) {
        int m = (l + r) / 2;
        if (calc(b, m) <= calc(a, m)) {
            r = m;
        } else {
            l = m + 1;
        }
    }
    return l;
}


int main(){

#ifndef ONLINE_JUDGE
     freopen("in.txt", "r", stdin);
#endif

    Rush {
        RD(n,l,p);++l;
        REP_1(i, n) s[i] = s[i-1] + strlen(RS(str[i])) + 1;

        cz = 0, op = 0; Q[0] = {0, n+1};

        REP_1(i, n) {
            //f[i] = OO; REP(j, i) if (checkMin(f[i], calc(j, i))) pre[i] = j;

            while (cz < op && Q[cz+1].se <= i) ++cz;
            f[i] = calc(pre[i] = Q[cz].fi, i);
            int j = left(Q[op].fi, i);
            while (cz < op && j <= Q[op].se) j = left(Q[--op].fi, i);

            Q[++op] = {i, j};
        }

        //REP_1(i, n) cout << f[i] << " "; cout << endl;
        //REP_1(i, n) cout << pre[i] << " "; cout << endl;

        if (f[n] > 1e18) puts("Too hard to arrange");
        else {
            printf("%.0Lf\n", f[n]);
            VI I; int x = n; I.PB(x);
            do I.PB(x = pre[x]); while (x);

            DWN(i, SZ(I), 1) {
                FOR(j, I[i]+1, I[i-1]) printf("%s ", str[j]);
                puts(str[I[i-1]]);
            }
        }
        puts("--------------------");
    }
}

Posted by xiaodao
Category: 日常