诗人小G 更清楚的理解

· · 个人记录

Luogu评测记录

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);
}