问题描述:

一首诗包含了若干个句子,对于一些连续的短句,可以将它们用空格隔开并放在一行中,注意一行中可以放的句子数目是没有限制的。小G给每首诗定义了一个行标准长度(行的长度为一行中符号的总个数),他希望排版后每行的长度都和行标准长度相差不远。显然排版时,不应改变原有的句子顺序,并且小G不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下,小G对于排版中的每行定义了一个不协调度, 为这行的实际长度与行标准长度差值绝对值的P次方,而一个排版的不协调度为所有行不协调度的总和。

小G最近又作了几首诗,现在请你对这首诗进行排版,使得排版后的诗尽量协调(即不协调度尽量小)。

输入:

输入文件中的第一行为一个整数T,表示诗的数量。

接下来为T首诗,这里一首诗即为一组测试数据。每组测试数据中的第一行为三个由空格分隔的正整数N,L,P,其中:N表示这首诗句子的数目,L表示这首诗的行标准长度,P的含义见问题描述。

从第二行开始,每行为一个句子,句子由英文字母、数字、标点符号等符号组成。

输出:

于每组测试数据,若最小的不协调度不超过10^18,则第一行为一个数,表示不协调度。接下来若干行,表示你排版之后的诗。注意:在同一行的相邻两个句子之间需要用一个空格分开。

如果有多个可行解,它们的不协调度都是最小值,则输出任意一个解均可。若最小的不协调度超过10^18,则输出“Too hard to arrange”(不含引号)。每组测试数据结束后输出“——————–”、。

思路:

这是一个DP应该不难想到,DP的方程也很简单:
$$f[i]=min\lbrace f[j]+\left|sum[i]-sum[j]+i-j-1-L\right|^p \rbrace $$

然后我们需要将它优化,斜率优化能过6,7两个点,但后面的就比较难了。我们可以利用四边形不等式证明出这个DP是有决策单调性的(证明与p次方有关,利用什么求导搞。。反正我不懂)。然后就可以利用决策单调性来优化DP啦。

决策单调性是指:设$p[i]$为$f[i]$的最优决策,那么对于所有$j>i$都有$p[j]>=p[i]$。我们利用这个性质,可以利用单调队列+二分,在$O(nlogn)$内完成DP。

单调队列中的元素包含3个值:$p, l, r$,表示在区间$[l, r]$中的最优决策都是$p$。首先是把$(0, 0, n)$入队,然后对于每一个i:
1. 先检查队头元素的$[l, r]$是否包含了i,如果不包含就直接出队
2. 利用队头元素的最优决策$p$来更新$f[i]$
3. 如果决策i比队尾的决策更优,那么我们就要插入决策i。于是我们就要找出区间$[l, r]$其中的最优决策都是i,首先$r$是为n(因为要靠后面决策来更新),$l$要利用二分找到。首先要清理队尾元素,也就是队尾元素整个区间$[l, r]$的决策i都更优,那么这个就可以出队。否则就在队尾元素区间$[l, r]$内二分,找到$l$的位置将决策i入队,并且更新队尾的$r$。

然后决策单调性的优化就是这样啦,自己理解了蛮久的。。。

代码

#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
#define LL long double
#define INF 1e18
#define MAXN 100005 
using namespace std;

int T, n, l, p, head, tail;
LL sum[MAXN], f[MAXN];
char str[MAXN];

struct Node {int p, l, r;} q[MAXN];

LL cal(int j, int i)
{
    LL num=1, x=sum[i]-sum[j]+i-j-1-l;
    for(int i=1; i<=p; i++) num*=abs(x);
    return f[j]+num;
}

int find(int l, int r, int j, int i)
{
    while(l<=r)
    {
        int mid=(l+r)>>1;
        if(cal(j, mid)<cal(i, mid)) l=mid+1;
        else r=mid-1;   
    }
    return l;
}

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d%d%d", &n, &l, &p);
        for(int i=1; i<=n; i++)
        {
            scanf("%s", str);
            int len=strlen(str);
            sum[i]=sum[i-1]+len;
        }

        head=1, tail=0;
        q[++tail]=(Node){0, 0, n};
        for(int i=1; i<=n; i++)
        {
            if(head<=tail && i>q[head].r) head++;
            f[i]=cal(q[head].p, i);
            if(head>tail || cal(i, n)<=cal(q[tail].p, n))
            {
                while(head<=tail && cal(i, q[tail].l)<=cal(q[tail].p, q[tail].l)) tail--;
                if(head>tail) q[++tail]=(Node){i, i, n};
                else
                {
                    int pos=find(q[tail].l, q[tail].r, q[tail].p, i);
                    q[tail].r=pos-1;
                    q[++tail]=(Node){i, pos, n};
                }
            }
        }

        if(f[n]>INF) printf("Too hard to arrange\n");
        else printf("%lld\n", (long long)f[n]);
        printf("--------------------\n");
    }
}

发表评论

邮箱地址不会被公开。 必填项已用*标注