[BZOJ 1563] [NOI 2009] 诗人小G(决策单调性)
题面
一首诗包含了若干个句子，对于一些连续的短句，可以将它们用空格隔开并放在一行中，注意一行中可以放的句子数目是没有限制的。小 G 给每首诗定义了一个行标准长度（行的长度为一行中符号的总个数），他希望排版后每行的长度都和行标准长度相差不远。显然排版时，不应改变原有的句子顺序，并且小 G 不允许把一个句子分在两行或者更多的行内。在满足上面两个条件的情况下，小 G 对于排版中的每行定义了一个不协调度, 为这行的实际长度与行标准长度差值绝对值的 P 次方，而一个排版的不协调度为所有行不协调度的总和。
小 G 最近又作了几首诗，现在请你对这首诗进行排版，使得排版后的诗尽量协调（即不协调度尽量小），并把排版的结果告诉他
\(n \leq 5\times 10^5\)
分析
转移方程推导
显然,设\(dp[i]\)为选了第\(i\)个句子并在此换行的最小不协调度。每句诗的长度为\(a[i]\),\(sum[i]\)为前\(i\)句诗的总长度，那么
\]
后面的式子表示把第\((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)\)
则只需证明
\]
即证明对于任意常数\(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");
}
}