NOI2009 诗人小G

@zryabc  July 31, 2019

题目

小G是一个出色的诗人,经常作诗自娱自乐。但是,他一直被一件事情所困扰,那就是诗的排版问题。

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

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

思路

需要用到决策单调性中一个叫二分栈(队列)的东西。

转移式子十分显然:

$$ dp[i]=min(dp[j]+w(j,i)) $$

然后打表发现决策是单调的。

重点来了

如何维护决策单调性呢?

决策单调性一般有以下几种维护方法:

  1. 四边形不等式
  2. 二分栈(队列)
  3. CDQ分治套分治
  4. WQS二分

这里先写一下二分栈(队列)

具体而言,这个队列维护的是区间的决策单调性的信息。队列中的元素有3个权值,$l,r,s$分别表示区间和这个区间对应的决策点。

假设某一状态下的决策点是:

11112222233344444445555566666777777777777777

那么新加入一个决策点8,它就可以从后往前把7,6,5这些可能不如它优的点弹掉。如果不能弹掉一整个块,就二分弹掉它的一部分,这样我们就成功维护了决策单调性了。

复杂度分析

对于每个决策点来说,它只可能进出队列一次,复杂度为$O(n)$。

计算每一个$dp[i]$,最坏情况下每次都要二分很大的序列,复杂度为$O(nlogn)$。

所以总复杂度为$O(nlogn)$。

代码

#include<bits/stdc++.h>
#define M 100005
#define LL long double
using namespace std;
const LL inf=1e18;
int n,L,P,T,A[M];
char S[35];
LL sum[M],dp[M];
LL calc(int i,int j){
    int y=abs(sum[i]-sum[j]+i-j-1-L);
    LL res=1;
    for(int i=1;i<=P;i++)res*=y;
    return dp[j]+res;
}
struct node{int l,r,s;}Q[M];
int main(){
    freopen("poet.in","r",stdin);
    freopen("poet.out","w",stdout);
    scanf("%d",&T);
    while(T--){
        scanf("%d%d%d",&n,&L,&P);
        for(int i=1;i<=n;i++){
            scanf("%s",S);
            sum[i]=sum[i-1]+strlen(S);
        }
        int l=1,r=0;
        Q[++r]=(node){1,n,0};
        for(int i=1;i<=n;i++){
            dp[i]=calc(i,Q[l].s);
            if(Q[l].l==Q[l].r)l++;
            else Q[l].l++;
            while(l<=r&&calc(Q[r].l,Q[r].s)>calc(Q[r].l,i))r--;
            if(l>r)Q[++r]=(node){i+1,n,i};
            else {
                int L=Q[r].l+1,R=Q[r].r+1;
                while(L<R){
                    int mid=(L+R)>>1;
                    if(calc(mid,Q[r].s)>calc(mid,i))R=mid;
                    else L=mid+1;
                }
                Q[r].r=L-1;
                if(L<=n)Q[++r]=(node){L,n,i};
            }
        }
        if(dp[n]>1e18)puts("Too hard to arrange");
        else printf("%.0Lf\n",dp[n]);
        puts("--------------------");        
    }
    return 0;
}

添加新评论