诗人小G问题

解题思路

本题要求整个诗句的总的不协调度最小。这是一个求方案最优解的问题，就可以考虑用 $dp$。

设 $a_i$ 表示第 $i$ 句诗的长度，$s_i$ 表示前 $i$ 句诗的总长度。

设 $f_i$ 表示安排完前 $i$ 句诗的不和谐度的最小值。

那么对于 $f_i$，我们可以枚举最后一句诗是多少来更新状态，得出状态转移方程：

$$ f_i = \min \lbrace f_j+ \vert s_i-s_j+i-j-1-L \vert^P \rbrace $$

我们设 $val(j,i) = s_i-s_j+i-j-1-L$。

我们尝试去证明 $val(j,i)$ 是满足四边形不等式的，这样我们就可以用四边形不等式优化。

要想证明 $val(j,i)$ 满足四边形不等式，就是要证明对于 $\forall j<i$，都有 $j<j+1\leq i<i+1$，就会有 $val(j,i+1)+val(j+1,i) \geq val(j,i)+val(j+1,i+1)$

整理得到：$val(j+1,i)-val(j+1,i+1) \geq val(j,i)+val(j,i+1)$

我们设 $u=val(j,i),v=val(j+1,i)$。

则此时 $val(j+1,i+1) = v+a_{i+1}+1，val(j,i+1) = u+a_{i+1}+1$

因此不等式就变成 $\vert v \vert^P-\vert v+a_{i+1}+1\vert^P \geq \vert u\vert^P-\vert u+a_{i+1}+1\vert^P$，接下来我们就是要证明整个不等式成立。

然后由于 $s_{j+1}>s_j,j+1>j$，因此可以得出 $u>v$。

然后可以发现不等式两边其实都是一个函数 $y(x)=\vert x\vert^P-\vert x+C\vert^P,C>0$，现在 $u>v$，但是我们要证明 $y(v) \geq y(u)$，因此这就等价于我们要证明函数 $y(x)$ 是单调递减的。

由于 $P>1$，因此分情况讨论，若 $P$ 是偶数，则 $y=x^P-(x+C)^P$，然后进行求导 $y’=Px^{P-1}-P(x+C)^{P-1}$，然后单独对 $x^{P-1}$ 进行求导，发现 $(P-1)x^{P-2}$ 是正的，因此 $x_{P-1}$ 就是单调递增的，因此 $x^{P-1} \leq (x+C)^{P-1}$，因此 $y’ \leq 0$，所以 $y$ 单调递减。

若 $P$ 是奇数，当 $-C\leq x \leq 0$ 时，此时 $y=-x^P-(x+C)^P$，则 $y’=-Px^{P-1}-P(x+C)^{P-1}$，由于 $P-1$ 是偶数，因此 $Px^{P-1}$ 和 $P(x+C)^{P-1}$ 都是正数，则整个 $y’$ 就 $\leq 0$，此时 $y$ 单调递减。当 $x < -C$ 时，则 $y=-x^P+(x+C)^P$，则 $y’=-Px^{P-1}+P(x+C)^{P-1}$，而 $\vert x \vert \geq \vert x+C \vert$，因此 $Px^{P-1} \geq P(x+C)^{P-1}$，所以 $y’ \leq 0$，所以 $y$ 单调递减。当 $x > 0$ 时，则 $y=x^P-(x+C)^P$，则 $y’=Px^{P-1}-P(x+C)^{P-1}$，显然 $x^{P-1} \leq (x+C)^{P-1}$，所以 $y’ \leq 0$，因此 $y$ 单调递减。

综上所述，在任何情况下，函数 $y(x)$ 都是单调递减的，由此证明 $val(j,i)$ 函数满足四边形不等式。

然后我们就能用四边形不等式优化 $dp$ 来做。关于四边形不等式优化 $dp$ 可参考：四边形不等式优化dp的相关概念

C++ 代码

#include <iostream>
#include <cstring>

using namespace std;

typedef long double LD;

const int N = 100010;

int n, L, P;
LD f[N]; //f[i] 表示安排完前 i 句诗的不和谐度的最小值
char str[N][31]; //记录所有诗句
int s[N]; //s[i] 表示前 i 句诗的总长度
int opt[N]; //opt[i] 表示第 i 阶段的最优决策
struct Node
{
    int j, l, r; //决策、左端点、右端点
}q[N]; //队列存储所有决策区间
int hh, tt;

LD val(int j, int i) //计算第 i 阶段的决策是 j 时 f[i] 的值
{
    LD res = 1, a = abs(s[i] - s[j] + i - j - 1 - L);
    for(int i = 0; i < P; i++) res *= a;
    return f[j] + res;
}

void insert(int i) //将决策 i 插入队列
{
    int pos = n + 1; //记录决策为 i 的区间的左端点
    //如果对队尾区间的第一个点来说，j 不如 i 好，就将队尾删掉
    while(hh <= tt && val(q[tt].j, q[tt].l) >= val(i, q[tt].l)) pos = q[tt--].l;
    //如果此时对于队尾区间的最后一个点来说，j 不如 i 好，说明 i 的位置应该在队尾区间中，二分 i 的位置
    if(hh <= tt && val(q[tt].j, q[tt].r) >= val(i, q[tt].r))
    {
        int l = q[tt].l, r = q[tt].r;
        while(l < r)
        {
            int mid = l + r >> 1;
            if(val(q[tt].j, mid) >= val(i, mid)) r = mid;
            else l = mid + 1;
        }
        q[tt].r = r - 1; //更新队尾长度
        pos = r; //更新决策为 i 的区间的左端点
    }
    if(pos != n + 1) q[++tt] = {i, pos, n}; //如果决策 i 有位置，将决策为 i 的区间插入
}

int main()
{
    int T;
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d%d", &n, &L, &P);

        for(int i = n; i >= 1; i--) scanf("%s", str[i]); //倒着接收字符串，这样输出方案时比较方便
        for(int i = 1; i <= n; i++) s[i] = s[i - 1] + strlen(str[i]); //预处理前缀和

        //最开始队列中所有位置的决策都是 0
        hh = 0, tt = 0;
        q[0] = {0, 1, n};
        for(int i = 1; i <= n; i++)
        {
            //此时队头就是最优决策，更新 f[i]，并记录方案
            f[i] = val(q[hh].j, i), opt[i] = q[hh].j;
            //f[i] 更新完后，i 的位置不用再维护，可以删掉，由于 i 一定在队头中，如果 i 在区间末尾，则整个区间删掉
            if(q[hh].r == i) hh++;
            q[hh].l = i + 1; //否则 i 一定在区间中间，则我们令队头的左端点为 i + 1，这样 i 就不在区间中了
            insert(i); //将决策 i 插入队列
        }

        if(f[n] > 1e18) puts("Too hard to arrange"); //无解
        else //否则有解，输出方案
        {
            printf("%lld\n", (long long)f[n]);
            //由于是倒着接收字符串的，因此我们倒着推出的方案刚好就是正的，不需要再额外处理
            for(int i = n; i; i = opt[i])
            {
                for(int j = i; j > opt[i]; j--)
                {
                    printf("%s", str[j]);
                    if(j != opt[i] + 1) printf(" ");
                }
                puts("");
            }
        }
        puts("--------------------");
    }
    return 0;
}