BZOJ1563 NOI2009诗人小G（动态规划+决策单调性）

　　设f[i]为前i行的最小不协调度，转移枚举这一行从哪开始，显然有f[i]=min{f[j]+abs(s[i]-s[j]+i-j-1-m)}。大胆猜想有决策单调性就好了。证明看起来很麻烦，从略。注意需要全程long double。

#include<bits/stdc++.h>

using namespace std;

int read()

{

    int x=,f=;char c=getchar();

    while (c<''||c>'') {if (c=='-') f=-;c=getchar();}

    while (c>=''&&c<='') x=(x<<)+(x<<)+(c^),c=getchar();

    return x*f;

}

#define N 100010

#define inf 1000000000000000001ll

#define ll long long

#define ld long double

int T,n,m,p,a[N],from[N],stk[N],L[N],R[N],top;

ld f[N];

char s[N][];

void print(int n)

{

    if (n==) return;

    print(from[n]);

    for (int i=from[n]+;i<n;i++) printf("%s ",s[i]);

    puts(s[n]);

}

ld ksm(ld a,int k)

{

    ld s=;

    for (;k;k>>=,a*=a) if (k&) s*=a;

    return s;

}

ld calc(int i,int j){return f[j]+ksm(abs(a[i]-a[j]-m),p);}

int main()

{

#ifndef ONLINE_JUDGE

    freopen("c.in","r",stdin);

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

    const char LL[]="%I64d\n";

#else

    const char LL[]="%lld\n";

#endif

    T=read();

    while (T--)

    {

        n=read(),m=read()+,p=read();

        for (int i=;i<=n;i++) scanf("%s",s[i]),a[i]=a[i-]+strlen(s[i]);

        for (int i=;i<=n;i++) f[i]=inf,a[i]+=i;

        stk[top=]=;L[]=,R[]=n;

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

        {

            int l=,r=top;

            while (l<=r)

            {

                int mid=l+r>>;

                if (R[mid]>=i) from[i]=stk[mid],r=mid-;

                else l=mid+;

            }

            f[i]=calc(i,from[i]);

            while (L[top]>i&&calc(L[top],i)<calc(L[top],stk[top])) top--;

            l=max(L[top],i+),r=R[top];int x=R[top]+;

            while (l<=r)

            {

                int mid=l+r>>;

                if (calc(mid,i)<calc(mid,stk[top])) x=mid,r=mid-;

                else l=mid+;

            }

            R[top]=x-;if (x<=n) stk[++top]=i,L[top]=x,R[top]=n;

        }

        if (f[n]<inf) printf(LL,(ll)f[n]),print(n);

        else puts("Too hard to arrange");

        for (int i=;i<=;i++) putchar('-');if (T) printf("\n");

    }

    return ;

}