[BZOJ] 1563: [NOI2009]诗人小G

1D/1D的方程，代价函数是一个p次函数，典型的决策单调性

用单调队列（其实算单调栈）维护决策点，优化转移

复杂度\(O(nlogn)\)

#include<iostream>

#include<cstring>

#include<cstdio>

using namespace std;

const int MAXN = 100005;

typedef long double ll;

struct Node{

    int l,r,p;

    Node(int _l=0,int _r=0,int _p=0){l=_l;r=_r;p=_p;}

}q[MAXN];

ll f[MAXN],s[MAXN];

int T,n,len;

ll p;

ll qpow(ll x,int y){

    if(x<0)x=-x;

    ll ret=1ll;

    while(y){

        if(y&1)ret*=x;

        x*=x;

        y>>=1;

    }

    return ret;

}

ll calc(int x,int y){return f[x]+qpow(s[y]-s[x]-len,p);}

int fnd(const Node &x,int y){

    int l=x.l,r=x.r+1,p=x.p,mid,ret=l;

    while(l<r){

        mid=(l+r)>>1;

        if(calc(y,mid)<=calc(p,mid))r=mid;

        else l=mid+1;

    }

    return l;

}

char str[32];

void solve(){

    cin>>n>>len>>p;len++;

    s[0]=0;f[0]=0;

    for(int i=1;i<=n;i++){

        scanf("%s",str);

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

    }

    int h=1,t=0;

    q[++t]=Node(1,n,0);

    for(int i=1;i<=n;i++){

        while(h<=t&&q[h].r<i)h++;

        f[i]=calc(q[h].p,i);

        if(calc(i,n)<=calc(q[t].p,n)){

            while(h<=t&&calc(i,q[t].l)<calc(q[t].p,q[t].l))t--;

            if(h>t){q[++t]=Node(i+1,n,i);continue;}

            int x=fnd(q[t],i);

            q[t].r=x-1;q[++t]=Node(x,n,i);

        }

    }

    if(f[n]>1e18){puts("Too hard to arrange");return;}

    printf("%.0Lf\n",f[n]);

}

int main(){

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

    cin>>T;

    while(T--)solve(),puts("--------------------");

}