P1912 题解

CatWing · 2025-07-16 14:12:45 · 题解

前置知识：决策单调性优化DP

四边形不等式：对于函数 g(x,y)，如果所有整数 a \le b \le c \le d，都有 g(a,d)+g(b,c) \ge g(a,c)+g(b,d)，则函数 g 满足四边形不等式，为凸函数 （可以记为包含大于等于交叉）

另一种形式（常见）：对于函数 g(x,y)，如果所有整数 a<b，都有 g(a,b+1)+g(a+1,b) \ge g(a,b)+g(a+1,b+1)，则函数 g 满足四边形不等式，为凸函数

如果DP转移方程为 f_i=min(f_j+g(j,i)),1 \le j<i，设 x_i 为 f_i 取到最小值时 j 的值，x_i 即为 f_i 的最优决策，若 x_i 单调不减，则称 f 具有决策单调性

若函数 g 满足四边形不等式，那么 f 有决策单调性

证明 f 有决策单调性后，可以把一个 O(n^2) 的DP优化到 O(nlogn) 甚至 O(n)

现在分析此题，先想朴素DP，设 f_i 为前 i 个句子的最小不协调度之和，s_i 是前 i 个短句的长度总和，那么有转移方程：

f_i=min(f_j+|s_i-s_j-(i-j+1)|^P)

意为前 j 行的代价加上把 j+1 ~ i 分到一行的代价

令函数 g(j,i)=|s_i-s_j-(i-j+1)|^P，现在要证明它满足四边形不等式，不会写QAQ，看一下这里（源自巨佬的博客）

~~好了我们证明完了~~，此时 f 有决策单调性

当求出 f_i 时，考虑它可以转移到哪些位置上去，根据决策单调性，对于 i 一定在 x 数组（见前置知识）中有一个位置 k 满足 k 前的最优决策都比 i 好，而后面的都比 i 差，那么可将 k 后的最优决策都设为 i

逐一修改时间复杂度太高，使用单调队列

建立一个结构体 q 模拟单调队列，内含三个元素 w,l,r，表示 x_l ~ x_r 的值都是 w

初值设 head=1,tail=0，对于每个 i，执行以下操作：

取出队首 (w_s,l_s,r_s)，若 r_s \le i，表示上一个最优决策的适用范围在 i 之前，那么直接删除，否则令 l_s=i，缩小范围 （要使用while）
取出队首保存的最优决策 w 进行转移，得到 f_i
插入新决策 i

取出队尾 (w_t,l_t,r_t)
如果对于 f_{l_t}，i 比 w_t 决策更优（f_i+g(i,l_t) \le f_{w_t}+g(w_t,l_t)），由于单调性，对于整个区间 [l_t,r_t]，i 都会比 w_t 更优，所以令 k=l_t，删掉队尾，返回步骤 1 （要使用while）
如果对于 f_{r_t}，w_t 比 i 决策更优，表示无需更改队尾，则去往步骤 5
否则，在 [l_t,r_t] 中二分查找位置 k，满足 k 之前的决策优于 i，之后的 i 更优，将 [l_t,r_t] 更改为 [l_t,k-1]
把 (i,k,n) 加到队尾，相当于决策 i 的适用范围是 [k,n]
整体逻辑就是新的决策 i 是否比旧的 w_t 更优，如果想（2）全都更优，则 i 的决策范围涵盖整个 [l_t,r_t]，否则如（4）找到那个令 i 更优的位置 k，最后加入新决策 i 及其范围，因为右边界无法计算，所以设定为 n

二分边界为 [l_t,r_t]，查找满足 g(i,k) \le g(w_t,k) 最小的 k，找到决策 i 的范围左边界

优化感性理解：首先，不断删除已经不适用的队头，最后剩的队头就是最优决策点，可依此进行转移；其次，将加入新的点 i 后，不满足单调递增的队尾弹出，并设定左边界将 i 加入队尾

总时间复杂度 O(nlogn)

Code:

#include <bits/stdc++.h>
using namespace std;
long long n,m,p,s[500005],k[500005],x[100005],z[500021];
long double f[500005];
char c[100005][35];
long double ksm(long double a,long long b)
{
    long double ans = 1;
    while(b != 0)
    {
        if(b % 2 == 1)
        {
            ans *= a;
        }
        a *= a;
        b /= 2;
    }
    return ans;
}
long double g(long long i,long long j)
{
    return f[i] + ksm(abs(s[j] - s[i] + j - i - 1 - m),p);
}
long long bs(long long a,long long b)
{
    if(g(a,n) < g(b,n))
    {
        return n + 1;
    }
    long long l = b,r = n,ans = n + 1;
    while(l <= r)
    {
        long long mid = (l + r) / 2;
        if(g(b,mid) <= g(a,mid))
        {
            r = mid - 1;
            ans = mid;
        }
        else
        {
            l = mid + 1;
        }
    }
    return ans;
}
int main()
{
    long long t;
    scanf("%lld",&t);
    while(t--)
    {
        scanf("%lld%lld%lld",&n,&m,&p);
        for(long long i = 1;i <= n;i++)
        {
            getchar();
            scanf("%s",c[i]);
            s[i] = s[i - 1] + strlen(c[i]);
            z[i] = 0;
        }
        long long hd = 1,tl = 1;
        for(long long i = 1;i<=n;i++)
        {
            while(hd < tl && bs(k[hd],k[hd + 1]) <= i)
            {
                hd++;
            }
            z[i] = k[hd];
            f[i] = g(k[hd],i);
            while(hd < tl && bs(k[tl - 1],k[tl]) >= bs(k[tl],i))
            {
                tl--;
            }
            k[++tl] = i;
        }
        if(f[n] > 1e18)
        {
            printf("Too hard to arrange\n");
        }
        else
        {
            printf("%lld\n",(long long)f[n]);
            long long cnt = 0;
            for(long long i = n;i != 0;i = z[i])
            {
                x[++cnt] = i;
            }
            x[++cnt] = 0;
            for(long long i = cnt;i >= 2;i--)
            {
                for(long long j = x[i] + 1;j <= x[i - 1] - 1;j++)
                {
                    printf("%s ",c[j]);
                }
                printf("%s\n",c[x[i - 1]]);
            }
        }
        printf("--------------------\n");
    }
    return 0;
}

注意：这题要求答案超过 10^{18} 就输出Too hard ...，所以使用long long存储不开，要使用long double，但是不仅 f 数组要开long double，ksm,g 函数以及快速幂 a^b 中的 a 也要开！ ~~（精度坑死人~~

P1912 题解

码字不易，猫猫求赞