记录编号	385761	评测结果	AAAAAAAAAA
题目名称	[NOI 2009]诗人小G	最终得分	100
用户昵称	FoolMike	是否通过	通过
代码语言	C++	运行时间	1.649 s
提交时间	2017-03-22 13:49:33	内存使用	7.16 MiB

#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
typedef long long ll;
typedef long double db;
const int N=1e5+10;
db dp[N],s[N];
char S[N][32];
int n,l,p,from[N],q[N],size;
db mi(db x){
	db ans=1;
	for (int y=0;y<p;y++) ans*=x;
	return ans<0?-ans:ans;
}
int L[N],R[N];//[L[i],R[i]]表示决策i支配的区间 
db val(int i,int j){return dp[j]+mi(s[i]-s[j]-l);}
void update(int k){
	if (val(n,q[size])<=val(n,k)) return;
	for (;val(L[size],q[size])>val(L[size],k);size--);
	int last=q[size],left=max(L[size],k+1),right=n;
	while (left<right){
		int mid=(left+right)>>1;
		if (val(mid,last)>val(mid,k)) right=mid;else left=mid+1; 
	}
	R[size]=left-1;
	q[++size]=k;L[size]=left;R[size]=n;
}
int main()
{
	freopen("noi09_poet.in","r",stdin);
	freopen("noi09_poet.out","w",stdout); 
	int T;
	scanf("%d",&T);
	while (T--){
		scanf("%d%d%d",&n,&l,&p);l++;
		for (int i=1;i<=n;i++){
			scanf("%s",S[i]);
			s[i]=s[i-1]+1+strlen(S[i]);
		}
		q[size=0]=0;L[0]=0;R[0]=n;
		for (int i=1,now=0;i<=n;i++){
			while (R[now]<i) now++;
			from[i]=q[now];
			dp[i]=val(i,q[now]);
			update(i);
		}
		if (dp[n]>1e18){
			puts("Too hard to arrange");
			goto end;
		}
		printf("%.0Lf\n",dp[n]);
		size=0;
		for (int i=n;i;i=from[i]) q[++size]=i;
		q[++size]=0;
		for (int i=size-1;i;i--){
			for (int j=q[i+1]+1;j<q[i];j++) printf("%s ",S[j]);
			puts(S[q[i]]);
		}
		end:
		for (int i=0;i<20;i++) putchar('-');
		puts("");
	}
	return 0;
}