P1880 [NOI1995] 石子合并
f
i
,
j
=
m
a
x
(
f
i
,
k
+
f
k
+
1
,
j
)
+
w
i
,
j
f_{i,j}=max(f_{i,k}+f_{k+1,j})+w_{i,j}
fi,j=max(fi,k+fk+1,j)+wi,j
若
w
i
,
j
w_{i,j}
wi,j满足区间单调性和四边形不等式，则
f
i
,
j
f_{i,j}
fi,j满足四边形不等式
p
i
,
j
p_{i,j}
pi,j为
f
i
,
j
f_{i,j}
fi,j的最优转移点
若
f
i
,
j
f_{i,j}
fi,j满足四边形不等式，则
p
i
,
j
−
1
<
=
p
i
,
j
<
=
p
i
+
1
,
j
p_{i,j-1}<=p_{i,j}<=p_{i+1,j}
pi,j−1<=pi,j<=pi+1,j
f
i
,
j
=
m
i
n
(
f
i
−
1
,
k
+
w
k
+
1
,
j
)
f_{i,j}=min(f_{i-1,k}+w_{k+1,j})
fi,j=min(fi−1,k+wk+1,j)，反证法证决策单调
P4072 [SDOI2016] 征途
CF321E Ciel and Gondolas 二维前缀和+分治优化
CF868F Yet Another Minimization Problem
决策单调，分治然后暴力更新区间信息，因为每个递归层区间端点最多移动
n
n
n次，一共
l
o
g
n
log n
logn个递归层，所以均摊
O
(
1
)
O(1)
O(1)
CF1527E
猜有决策单调，然后暴力dp验证
经典分段问题，决策单调分治，然后求
c
a
l
(
i
,
j
)
cal(i,j)
cal(i,j)，类似上题可证时间复杂度是可过的
P5574 [CmdOI2019] 任务分配问题
思路类似上一题，只不过更新区间时多套一个树状数组辅助更新即可
Zombies
很像邮局那种，我们肯定是将区间中点靠得比较近的区间交给一个自动的机器管理即可，所以先将区间排序
然后转换为2D1D类经典问题，先分析这个dp肯定是满足决策单调的，接下来就是如何快速求
w
i
,
j
w_{i,j}
wi,j
易证机器开始区间肯定是在某个区间左端点，或者结束区间时某个区间右端点，所以正常可以枚举
i
,
j
i,j
i,j，然后枚举开始的时间，然后再遍历一遍
i
,
j
i,j
i,j区间
O
(
n
4
)
O(n^4)
O(n4)，然后预处理前缀和可以做到
O
(
n
3
)
O(n^3)
O(n3)
容易证明它也是具有决策单调性的，可以优化到
o
(
n
2
)
o(n^2)
o(n2)
最后分治优化dp
证明决策单调，然后用单调队列维护每个点作为最优决策点的范围，每次加入点 二分更新
int head=1,tail=0;
q[++tail]=node{0,n+1};
for (int i=1;i<=n;i++){
while (head<tail&&q[head].r<=i){
head++;
}
f[i]=f[q[head].pos]+cal(q[head].pos+1,i);
pre[i]=q[head].pos;
while (head<tail&&find(q[tail].pos,i)<=q[tail-1].r){
tail--;
}
q[tail].r=find(q[tail].pos,i);
q[++tail]=node{i,n+1};
}
P1912 [NOI2009] 诗人小G
常规分组，记录一下转移点即可
P3515 [POI2011] Lightning Conductor
转换一下式子，分成两次dp，每次可以决策单调优化
P6246 [IOI2000] 邮局 加强版
The 2018 ACM-ICPC Asia Nanjing Regional Programming Contest B
先wqs二分，然后转换为1D1D类