诗人小G 更清楚的理解

class Solution_Case
{
	/*
	诗人小G ×
	诗人握持 √

	设F[i]为对前i首诗排版的最小不协调度，a[i]为第i句诗的长度，sum[i]为前i句诗的总长度
	设val(i,j)为 abs( sum[i]-sum[j] + i-j-1 - L )^P
	dp方程可以写作：F[i]=min(F[j]+val(i,j))

	尝试证明val满足四边形不等式：val(j,i+1) + val(j+1,i) >= val(j,i) + val(j+1,i+1)
	前一项相等放一起：val(j+1,i) - val(j+1,i+1) >= val(j,i) - val(j,i+1)
	把式子展开，用符号代替相同部分。
	|v|^p - |v+(a[i+1]+1)|^p >= |u|^p - |u+(a[i+1]+1)|^p    ， u > v;
	证明对于任意c>0 函数y=|x|^p - |x+c|^p 单调递减 即可。
	利用微软计算器绘制函数图像显然可得的确是单调递减的，数学方法应为求导。

	然后按照算法竞赛进阶指南的思路，维护一个元组数组来应用决策单调性：
	每次我们求出一个i，这个i有可能会作为后面的i'的转移决策。
	我们从后面向前面查找一个位置，让这个位置左侧的最优决策是以前存的，右侧的最优决策是当前的i，
	这样由于决策单调性，我们就可以把这个位置以后的部分的最有决策全部更改为i。
	为了方便查找，我们可以采用三元组的方式，
	把每一段的最优决策集合存为一个区间，每次只要看端点是否更优，就可以一下子扔掉一个区间，以便加速。
	*/
};
#include<bits/stdc++.h>
#define N 100005
#define int long long
#define inf 0x3f3f3f3f3f3f3f3f
using namespace std;

typedef long double D;
const char END[] = "--------------------\n";
const char HARD[] = "Too hard to arrange\n";
const D lim = 1e18;
void Print_Ans();

int T, n, L, P;
int a[N], sum[N], fa[N];
D f[N];
char S[N][35];
struct node
{
	int L, R, j;
} q[N];
int l, r;

D Pow(D a, int b, D ans = 1)	//幂
{
	while (b)
	{
		if (b & 1) ans = ans * a;
		a = a * a;
		b >>= 1;
	}
	return ans;
}

D val(int i, int j)
{
	int tmp = sum[i] - sum[j] + i - j - 1 - L;
	return Pow(abs(tmp), P);
}

D GetState(int state, int chose)	//【状态】由【决策】转移
{
	return f[chose] + val(state, chose);
}

void Update(int i)
{
	while (l <= r && GetState(q[r].L, i) <= GetState(q[r].L, q[r].j)) r--;	//i更优，后面都要换成i，看下一组

	int LL = q[r].L, RR = n + 1, pos = n + 1;	//pos为i能管到的最小位置
	while (LL <= RR)
	{
		int mid = (LL + RR) / 2;
		if (GetState(mid, i) <= GetState(mid, q[r].j)) RR = mid - 1, pos = mid;	//mid之后i更优，往前面查找
		else LL = mid + 1;	//向后
	}

	if (pos > n) return;	//i没用
	q[r].R = pos - 1;	//原来的只能管到pos-1
	q[++r] = {pos, n, i};
}

signed main()
{
	scanf("%d", &T);
	while (T--)
	{
		scanf("%d %d %d", &n, &L, &P);
		for (int i = 1; i <= n; i++)
		{
			scanf("%s", S[i] + 1);
			a[i] = strlen(S[i] + 1);
			sum[i] = sum[i - 1] + a[i];
			f[i] = 1e19;
		}

		f[0] = 0;
		l = 1, r = 1, q[1] = {1, n, 0};

		for (int i = 1; i <= n; i++)
		{
			while (l <= r && q[l].R < i) l++;	//弹出无用三元组
			int j = q[l].j;
			f[i] = GetState(i, j), fa[i] = j;	//转移
			Update(i);
		}

		Print_Ans();
	}
}


void Print_Ans()
{
	if (f[n] > lim)
	{
		printf("%s%s", HARD, END);
		return ;
	}
	printf("%.0Lf\n", f[n]);
	stack<int> stk;
	for (int i = n; i; i = fa[i]) stk.push(i);
	int old = 1, now = 0;
	while (!stk.empty())
	{
		now = stk.top();
		stk.pop();
		for (int i = old; i < now; i++) printf("%s ", S[i] + 1);
		printf("%s\n", S[now] + 1);
		old = now + 1;
	}
	printf("%s", END);
}