[BZOJ 1563] [NOI 2009] 诗人小G(决策单调性)

题面

分析

转移方程推导

显然,设\(dp[i]\)为选了第\(i\)个句子并在此换行的最小不协调度。每句诗的长度为\(a[i]\),\(sum[i]\)为前\(i\)句诗的总长度，那么

\[dp[i]=\min_{0 \leq j <i}(dp[j]+|sum[i|-sum[j]+(i-j-1)-L|^P)\]

后面的式子表示把第\((j,i]\)句分成一行的代价。句子长度为\(sum[i]-sum[j]\),空格长度为\(i-j-1\)

这里的\(w\)函数为\(w(j,i)=|sum[i|-sum[j]+(i-j-1)-L|^P\),由于\(P\)的次数较高,无法斜率优化。于是尝试证明\(w\)满足四边形不等式

决策单调性证明

我们要证明\(\forall j<i,w(j,i+1)+w(j+1,i) \geq w(j,i)+w(j+1,i+1)\)

移项，得\(w(j+1,i)-w(j+1,i+1) \geq w(j,i)-w(j,i+1)\)

记:

\(u=(sum[i]+i)-(sum[j]+j)-(L+1)\)

\(v=(sum[i]+i)-(sum[j+1]+j+1)-(L+1)\)

则只需证明

\[|v|^P=|v+(a[i+1|+1)|^P \geq |u|^P -|u+(a[i+1]+1)|^P\]

即证明对于任意常数\(c\),函数\(h(x)=|x|^P-|x+c|^P\)单调递减.证明比较繁琐，这里引用一下

总之,\(w\)满足四边形不等式,那么\(f\)有决策单调性

优化方法

由于单调性，每个决策\(x\)肯定存在一个区间\([l[x],r[x]]\)使得当前情况下\(p[k]=x(k \in[l[x],r[x]])\)，

记\(pos(x,y)\)表示当前情况下,第一个以\(x\)为决策点不如以\(y\)为决策点更优的位置(如果当前只计算到\(dp[i]\),则对于\(i'>i\),\(p[i']=i\))。则\(r[x]=l[y]=pos(x,y)\).\(pos\)可以二分查找求出。

我们维护一个单调队列存储决策点。在处理\(dp[i]\)时,我们这样做:

如果队头的决策点对应区间不包含i,即\(r[q[head]]=pos(q[head],q[head+1])<i\)则出队
通过队头决策点转移
通过二分寻找出最左边的，以\(q[tail]\)为决策点不如以i为决策点更优的位置。这个位置实际上是\(l[i]\).由于决策单调性，目前从这个位置往右的 dp 都满足以i为决策点是最优的。再二分出\(l[q[tail]]=pos(q[tail-1],q[tail])\),如果\(l[i]<r[q[tail]]\),说明\(q[tail]\)决策点对应的所有转移都不如\(i\)更优,我们把\(q[tail]\)出队,继续比较下一个决策点
当队尾的弹出停止的时候，将\(i\)入队，且\(i\)对应区间右端点为\(n\)

代码

#include<iostream>
#include<cstdio>
#include<algorithm>
#include<cstring>
#define maxn 500000
#define maxl 30
#define INF 1e18
using namespace std;
typedef long double db;
int T;
int n,L,P;
char s[maxn+5][maxl+5];
int sum[maxn+5];
db dp[maxn+5];
int res[maxn+5];
inline db fast_pow(db x,int k){
    db ans=1;
    while(k){
        if(k&1) ans=ans*x;
        x=x*x;
        k>>=1;
    }
    return ans;
}
inline db calc(int j,int i){//计算f[j]+val(j,i)
    return dp[j]+fast_pow(abs(sum[i]-sum[j]+(i-j-1)-L),P);
}
inline int bin_search(int a,int b){//找到第一个决策b比决策a优的位置
    if(calc(a,n)<calc(b,n)) return n+1;
    int l=b,r=n;
    int ans=-1;
    int mid;
    while(l<=r){
        mid=(l+r)>>1;
        if(calc(b,mid)<=calc(a,mid)){
            ans=mid;
            r=mid-1;
        }else l=mid+1;
    }
    return ans;
}
void ini(){
    for(int i=1;i<=n;i++){
        dp[i]=INF;
        res[i]=0;
    }
}

int q[maxn+5];
int stk[maxn+5];//找出1~n最优决策的每一段
int main(){
    scanf("%d",&T);
    while(T--){
        scanf("%d %d %d",&n,&L,&P);
        ini();
        for(int i=1;i<=n;i++){
            scanf("%s",s[i]);
            sum[i]=strlen(s[i])+sum[i-1];
        }
        int head=1,tail=0;
        q[++tail]=0;
        dp[0]=0;
        for(int i=1;i<=n;i++){
            while(head<tail&&bin_search(q[head],q[head+1])<=i) head++;
            //使得head决策点的对应区间包含i
            res[i]=q[head];
            dp[i]=calc(q[head],i);
            while(head<tail&&bin_search(q[tail-1],q[tail])>=bin_search(q[tail],i)) tail--;
            //把以队尾决策点为决策点不如以i为决策点更优的位置出队
            q[++tail]=i; //并替换成i
        }
        if(dp[n]>INF){
            printf("Too hard to arrange\n");
        }else{
            printf("%lld\n",(long long)dp[n]);
            int top=0;
            for(int i=n;i;i=res[i]) stk[++top]=i;
            stk[++top]=0;
            for(int i=top-1;i>=1;i--){
            int r=stk[i],l=stk[i+1]+1;
            for(int j=l;j<r;j++) printf("%s ",s[j]);
            printf("%s\n",s[r]);
            // }
        }
        printf("--------------------\n");
    }
}