决策单调性优化
对于最优化DP来说，即决策点具有单调性。
代码实现
分治
以 P5503 [JSOI2016] 灯塔 为例。
答案 \(p_i = \max\{\lceil h_j - h_i + \sqrt{|i-j|} \rceil\}\)。
去除绝对值，分到两种情况中去做，可以先不用考虑上取整，输出时再做即可。
我们先考虑 \(j \leq i\) 的情况，对于另外一种，将整个数组翻转过来即可。
设 \(f_j(i) = h_j + \sqrt{i-j}\)。
把 \(h_i\) 提出来，代入 \(f_j\)。
\[p_i = \lceil -h_i + \max\{f_j(i)\}\rceil \]本质上 \(f\) 是由同一个函数图像平移出来的。
由于递增容易发现的是每一个函数两两之间只有一个交点。
可以自行画图理解，决策单调性是比较显然的。
\(p_i\) 取值与 \(p_j\) 无关，这样的话我们就可以整体二分。
Solve(l,r,L,R) 表示求值区间 \([l,r]\) 决策区间 \([L,R]\)。
每一次，找到区间中点 \(mid\) 与其决策点 \(MID\)，记录答案后分到两边去做。
Solve(l,mid-1,L,MID) 与 Solve(mid+1,r,MID,R)。
时间复杂度 \(O(n \log n)\)
#include<bits/stdc++.h>
using namespace std;
const int maxn=5*1e5;
int n;
int a[maxn+5];
double p[maxn+5];
inline double Calc(int i,int j){
return a[j]-a[i]+sqrt(i-j);
}
void Solve(int l,int r,int L,int R){
if(l>r) return;
int mid=(r-l)/2+l,k;
double mx=0,val;
for(int i=L;i<=R&&i<=mid;i++){
val=Calc(mid,i);
if(val>=mx) mx=val,k=i;
}
p[mid]=max(p[mid],mx);
Solve(l,mid-1,L,k);
Solve(mid+1,r,k,R);
}
signed main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
Solve(1,n,1,n);
for(int i=1;i<=n/2;i++)
swap(a[i],a[n-i+1]),swap(p[i],p[n-i+1]);
Solve(1,n,1,n);
for(int i=1;i<=n/2;i++)
swap(a[i],a[n-i+1]),swap(p[i],p[n-i+1]);
for(int i=1;i<=n;i++) printf("%d\n",(int)ceil(p[i]));
return 0;
}
单调队列
以 P1912 [NOI2009] 诗人小G 为例。
令 \(s(i) = \sum_{j=1}^i (len[j]+1)\)。
设 \(f(i)\) 表示考虑到第 \(i\) 句时的答案。
有状态转移方程：
\[f(i) = f(j) + (s(i)-s(j)-1-L)^P \]打表发现其具有决策单调性，证明略过。
由于 \(f(i)\) 转移与 \(f(j)\) 有关，所以不能整体二分，可以用单调队列。
单调队列存储决策点。
由于决策单调性，我们可以用二分实现函数 Get(x,y) = k 表示决策 \(x\) 在 \([1,k]\) 中优于 \(y\)。
按照从小到大的顺序求 \(f\)。
首先是加入 \(0\)，初始时，其是所有 \(f\) 的最优决策点。
接着每一次计算 \(f_i\) 重复以下步骤。
- 当
Get(第一个,第二个) < i时弹出队头，因为它已不优。 - 更新并记录答案。
- 当
Get(倒数第二个,最后一个) >= Get(最后一个,i)弹出队尾，因为其既不优于倒数第二个，也不优于 \(i\)。 - 插入 \(i\)。
应该解释的比较清楚了。
对于本题，需要注意的是，使用 long double 存储答案，因为答案可能会很大，并且当答案很大时并不用输出，不用担心丢失精度。
#include<bits/stdc++.h>
using namespace std;
#define ll long long
#define ldb long double
const int maxn=2e5;
const int maxs=30;
int n,L,P;
char str[maxn+5][maxs+5];
ll s[maxn+5];
ldb f[maxn+5];
int g[maxn+5];
ll q[maxn+5];
int hd,tl;
inline ldb Fpow(ldb x,ll y){
ldb res=1;
if(x<0) x=-x;
for(;y;y>>=1,x*=x)
if(y&1) res*=x;
return res;
}
inline ldb Calc(int i,int j){
return f[j]+Fpow(s[i]-s[j]-L-1,P);
}
inline int Get(int x,int y){
int l=y,r=n,mid,ans=y-1;
while(l<=r){
mid=(l+r)/2;
if(Calc(mid,x)<=Calc(mid,y)) ans=mid,l=mid+1;
else r=mid-1;
}
return ans;
}
inline void Work(){
scanf("%d%d%d",&n,&L,&P);
for(int i=1;i<=n;i++){
scanf("%s",str[i]);
s[i]=s[i-1]+(ll)strlen(str[i])+1;
g[i]=0,f[i]=1e20;
}
hd=1,tl=0;
q[++tl]=0;
f[0]=0;
for(int i=1;i<=n;i++){
while(hd<tl&&Get(q[hd],q[hd+1])<i) hd++;
g[i]=q[hd],f[i]=Calc(i,q[hd]);
while(hd<tl&&Get(q[tl],i)<=Get(q[tl-1],q[tl])) tl--;
q[++tl]=i;
}
if(f[n]>1e18) puts("Too hard to arrange");
else{
printf("%lld",(ll)f[n]);
hd=1,tl=0;
for(int i=n;i>0;i=g[i]) q[++tl]=i;
q[++tl]=0;
for(;tl>0;tl--){
puts("");
for(int i=q[tl]+1;i<=q[tl-1];i++){
if(i<q[tl-1]) printf("%s ",str[i]);
else printf("%s",str[i]);
}
}
}
puts("--------------------");
}
signed main(){
int T;
scanf("%d",&T);
while(T--) Work();
return 0;
}