动态规划，方程是f[i]=min{f[j]+|sum[i]-sum[j]+i-j-1-L|^P}。
朴素的不能AC，要超时，然后要用四边形不等式优化，优化到O(nlogn)。
恩，四边形不等式优化正在研究中。
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 head,tail;
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;
head=tail=0;
begin[tail]=0;
end[tail]=N;
best[tail]=0;
for (int i=1;i<=N;i++)
{
while (end[head]<i) head++;
pre[i]=best[head];
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)
while (head<tail
&&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();
}