# NOI2009[诗人小G/poet]

CODE:

/*

PROGRAM: \$PROGRAM

AUTHOR: Su Jiao

DATE: 2010-5-27

DESCRIPTION:

\$DESCRIPTION

*/

#include <stdio.h>

#include <string.h>

#include <math.h>

class Application

{

FILE* in;

FILE* out;

static const int MAXLENGTH=50;

static const int MAXN=100000;

static const long long int oo=1000000000000000000ll;

typedef char string[MAXLENGTH+1];

int T;

int N,L,P;

string s[MAXN+2];

long long int sum[MAXN+2];

long long int f[MAXN+2];

int pre[MAXN+2];

int top;

int stack[MAXN+2];

int begin[MAXN+2],end[MAXN+2],best[MAXN+2];

void print_long_long_int(long long int number)

{

if (number>=10) print_long_long_int(number/10);

fprintf(out,“%d”,number%10);

}

static long long int abs(long long int n)

{

return n>0?n:-n;

}

static long long int power(long long int b,long long int p)

{

long long int get=1;

while (p)

{

if (p&1) get*=b;

b*=b;

p>>=1;

}

return get;

}

void solve()

{

sum[0]=0;

for (int i=1;i<=N;i++)

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

//f[i]=min{f[j]+|sum[i]-sum[j]+i-j-1-L|^P}

/*

f[0]=0;

for (int i=1;i<=N;i++)

{

double min=oo*2;

for (int j=0;j<i;j++)

{

double get=f[j]+pow(fabs(sum[i]-sum[j]+i-j-1-L),P);

if (get<min)

{

min=get;

pre[i]=j;

}

}

if (f[pre[i]]+pow(fabs(sum[i]-sum[pre[i]]+i-pre[i]-1-L),P)<oo*2)

{

f[i]=f[pre[i]]+power(abs(sum[i]-sum[pre[i]]+i-pre[i]-1-L),P);

if (f[i]>oo) f[i]=oo+1;

}

else f[i]=oo+1;

}

*/

f[0]=0;

begin[tail]=0;

end[tail]=N;

best[tail]=0;

for (int i=1;i<=N;i++)

{

if (f[pre[i]]+pow(fabs(sum[i]-sum[pre[i]]+i-pre[i]-1-L),P)<oo*2)

{

f[i]=f[pre[i]]+power(abs(sum[i]-sum[pre[i]]+i-pre[i]-1-L),P);

if (f[i]>oo) f[i]=oo+1;

}

else f[i]=oo+1;

#define value(now,pre) \

f[pre]+pow(fabs(sum[now]-sum[pre]+now-pre-1-L),P)

&&value(begin[tail],i)<value(begin[tail],best[tail]))

end[tail-1]=end[tail],tail–;

int l=begin[tail],r=end[tail]+1;

while (l+1!=r)

{

int mid=(l+r)>>1;

if (value(mid,best[tail])<value(mid,i)) l=mid;

else r=mid;

}

if (l+1<=end[tail])

{

tail++;

begin[tail]=l+1;

end[tail]=end[tail-1];

best[tail]=i;

end[tail-1]=l;

}

#undef value

}

if (f[N]>oo) fprintf(out,“Too hard to arrange\n”);

else

{

print_long_long_int(f[N]);

fprintf(out,“\n”);

stack[top=0]=N;

while (stack[top])

stack[top+1]=pre[stack[top]],top++;

for (int i=top;i>0;i–)

for (int j=stack[i]+1;j<=stack[i-1];j++)

fprintf(out,“%s%c”,s[j],j==stack[i-1]?’\n’:’ ‘);

}

fprintf(out,“——————–\n”);

}

public:

Application(const char* input,const char* output)

:in(fopen(input,“r”)),out(fopen(output,“w”))

{

fscanf(in,“%d”,&T);

}

~Application()

{

fclose(in);

fclose(out);

}

int run()

{

for (int i=0;i<T;i++)

{

fscanf(in,“%d%d%d”,&N,&L,&P);

for (int i=1;i<=N;i++)

fscanf(in,“%s”,s+i);

solve();

}

}

};

int main()

{

static

Application app(“poet.in”,“poet.out”);

return app.run();

}