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

题面

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

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

(n leq 5 imes 10^5)

分析

转移方程推导

显然,设(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
");
		}else{
			printf("%lld
",(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
",s[r]);
			// } 
		}
		printf("--------------------
");
	}
}