[NOI2009]诗人小G 题解
Link
我们应该可以想到一个这样的转移方程:
\(dp[i]=\min \limits^{i-1}_{j=1}(dp[i],dp[j]+|sum[i]-sum[j]-L-1|^p)\),
其中\(dp[i]\)表示排版完前\(i\)句的最小不协调度,记\(sum[i]=\sum\limits^{i}_{j=1}+i\)(默认每句后有空格),我们就能得到这个\(O(n^2)\)的转移方程然而显然过不了.
那怎么办呢?
当\(p=2\)时,显然我们可以使用斜率优化来解决这道题,但是......因此,我们需要寻找一种适用范围在这道题更为广阔的方法.
通过严谨的猜想与证明打表,我们可以发现,对于\(j<i\),\(dp[i]\)的最优决策点总是比\(dp[j]\)要大,这说明什么?最优决策点单调递增.
我们可以把一个决策点\(p\)的转移函数画出来,设其为\(f_{p}(i)\),我们知道,又因为\(f_p'(i)=p|sum[i]-sum[j]-L-1|^{p-1}\)单调递增,那么对于两个决策函数\(f_{i},f_{j}\)只会有一个交点,在这个交点之后,\(f_{i}\)就再也追不上\(f_{j}\)了.
那么,对于每一个决策点\(p\),它只会是一段连续区间的最优决策点,我们可以记录一个三元组\(<L,R,pos>\)表示在\(L\)到\(R\)这段区间里,最优决策点是\(pos\).我们可以用一个单调队列维护这个东西.
具体的,对于新加入一个位置,我们二分出上一个决策点的转移函数和当前位置转移函数的交点,那就可以更新上一个决策点区间的右端点和这一个新加入的决策点区间的左端点.若某决策点的右端点已经小于当前位置,直接从队列里弹出.若某决策点其决策函数在其左端点处的函数值比当前位置的决策函数在同一位置时的函数值大,那么那个决策点也没有存在的必要了.
注意\(dp\)值域过大,要开long double换取更大的值域.
Code
#include <bits/stdc++.h>
#define LD long double
using namespace std;
int T,N,L,P,l,r;
char s[100005][35];
LD dp[100005],sum[100005];
int ans[100005],pre[100005];
struct Queue{
int l,r,pos;
}q[100005];
inline int read(){
int x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-')f=-1;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=(x<<1)+(x<<3)+ch-'0';
ch=getchar();
}
return x*f;
}
inline LD quick_power(LD x,int k){
LD res=1;
while(k){
if(k&1)
res=res*x;
x=x*x;k>>=1;
}
return res;
}
inline LD Get(int i,int j){
if(i<j)swap(i,j);
return dp[j]+quick_power(abs(sum[i]-sum[j]-L),P);
}
inline int Binary_find(int k,int i){
int l=q[k].l,r=q[k].r;
int res=r+1,pos=q[k].pos;
while(l<=r){
int mid=l+r>>1;
if(Get(i,mid)<=Get(pos,mid))
res=mid,r=mid-1;
else
l=mid+1;
}
return res;
}
int main(){
T=read();
while(T--){
N=read();L=read()+1;P=read();
for(register int i=1;i<=N;++i){
scanf("%s",s[i]);
sum[i]=sum[i-1]+strlen(s[i])+1;
}
q[l=r=1]=(Queue){1,N,0};
for(register int i=1;i<=N;++i){
while(l<r&&q[l].r<i)
++l;
++q[l].l;
pre[i]=q[l].pos;
dp[i]=Get(i,q[l].pos);
while(l<r&&Get(q[r].l,q[r].pos)>=Get(q[r].l,i))
--r;
int pos=Binary_find(r,i);
if(pos<=N){
q[r].r=pos-1;
q[++r]=(Queue){pos,N,i};
}
}
if(dp[N]>1e18)
printf("Too hard to arrange\n");
else{
int now=N,cnt=0;
printf("%lld\n",(long long)dp[N]);
while(now){
ans[++cnt]=now;
now=pre[now];
}
ans[cnt+1]=0;
for(register int i=cnt;i;--i){
for(register int j=ans[i+1]+1;j<=ans[i];++j){
printf("%s",s[j]);
if(j!=ans[i])
putchar(' ');
}
putchar('\n');
}
}
printf("--------------------\n");
}
return 0;
}