动态规划的优化

单调队列优化多重背包

先枚举物品，然后枚举余数，然后再枚举转移状态

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
	int ans=0;
	for(int i=1;i<=n;i++){
		int vi,wi,si;
		cin>>vi>>wi>>si;
		if(vi==0) ans+=wi*si;//特判
		si=min(si,v/vi);//真正可用物品数量 
		for(int d=0;d<vi;d++){//枚举余数 
			deque<pii> q;
			int k=(v-d)/vi;//可以转移的状态数量 
			for(int j=0;j<=k;j++){
				int now=dp[d+j*vi]-j*wi;//生成一个新状态，注意要-j*wi。后面还会加回来 
				while(!q.empty()&&now>=q.back().first) q.pop_back();
				q.push_back(pii(now,j));
				while(!q.empty()&&q.front().second+si<j) q.pop_front();
				dp[d+j*vi]=max(dp[d+j*vi],q.front().first+j*wi); 
			}
		}
	}
	cout<<ans+dp[v];

加入状态的时候 $-j\times wi$，取出状态的时候 $+j\times wi$

四边形不等式优化

dp形式与结论

（1） $dp[l][r]=min(dp[l][k]+dp[k+1][r])+w(l,r)$

若dp方程满足四边形不等式，设 $d[l][r]$ 为 $dp[l][r]$ 的最优决策点，则有 $d[l][r-1] \leq d[l][r] \leq d[l+1][r]$

（2） $dp[i][j]=min(dp[i-1][k])+w(k,j)$

若dp方程满足四边形不等式，设 $d[i][j]$ 为 $dp[i][j]$ 的最优决策点，则有 $d[i-1][j] \leq d[i][j] \leq d[i][j+1]$

使用四边形不等式优化

我们需要证明 $w(i,j)$ 这个二元函数满足区间包含单调性和四边形不等式，才能说明dp满足四边形不等式

1. 区间包含单调性
   若 $l \leq l' \leq r' \leq r$ 则 $w(l',r') \leq w(l,r)$

2. 四边形不等式
   若 $l \leq l' \leq r' \leq r$ 则 $w(l,r')+w(l',r) \leq w(l,r)+w(l'+r')$

此外还有如下结论帮助我们证明：

1. 如果 $f(l,r)$ 和 $g(l,r)$ 符合四边形不等式/区间包含单调性，则对于任意 $A,B \geq 0$ 都有 $Af(l,r)+Bg(l,r)$ 也符合四边形不等式/区间包含单调性

2. 如果存在 $f(x)$ 和 $g(x)$ 使 $w(l,r)=f(r)-g(l)$ ，则 $w(l,r)$ 符合四边形恒等式（即总是等号成立的四边形不等式）。如果 $f,g$ 单调递增，那么 $w$ 还符合区间包含单调性

3. 若 $h(x)$ 单调递增且下凸（$h'(x)$ 单调递增）,$w(l,r)$ 符合四边形不等式和区间包含单调性，则 $h(w(l,r))$ 也符合四边形不等式和区间包含单调性

避免证明四边形不等式

将dp最优决策点 $d[i][j]$ 数组打表，如果发现每一行、每一列都具有单调性，那么可以大胆赌一把dp满足四边形不等式

斜率优化

如果转移方程中，dp的当前位置i和准备转移到当前位置的决策点j存在形如 $g(i)*f(j)$ 的一项，那么大概率可以使用斜率优化

将转移方程进行整理，由于当前dp到的位置i是固定的，因此所有与i有关的变量（除了 $dp[i]$ ）都视为常数。将含有 $j$ 的变量标记出来，将其移项，使得等式的一边只有一项带有 $j$，其余和 $j$ 有关的都移到另一边，这样我们就可以整理得到形如 $y=kx+b$ 的式子，并且我们要求的 $dp[i]$ 会在b这个位置。按题目要求，我们最大化/最小化截距。

按照上面的式子，对于每个决策点，我们将其在二维平面上表示为点 $(x,y)$。然后做斜率为k的直线并进行平移，使得截距取得最值。$k$ 叫做目标斜率。要想快速得到最优决策点，我们需要维护一个凸壳。

一般来说，题目要求最小值，我们维护下凸壳，求最大值，我们维护上凸壳

下凸壳的点集，相邻点连线的斜率是单调递增的。下凸壳的点集，斜率则是单调递减的

按照凸壳方向和目标斜率之间的关系，我们分为下面几类

单调队列维护

下凸壳，目标斜率递增；上凸壳，目标斜率递减

使用单调队列维护

首先我们需要找到最优决策点。这个点和上个点的斜率需要小于目标斜率，和下一个点的斜率需要大于目标斜率。不满足的点直接移出单调队列

cpp
1
2
while(head<tail&&slope(que[head],que[head+1])<目标斜率) head++;
dp[i]=...通过que[head]进行转移

然后准备加入新的决策点i。加入之前，还需要维护凸壳的单调性

cpp
1
2
while(head<tail&&slope(que[tail],que[tail-1])>slope(que[tail],i)) tail--;
que[++tail]=i;

单调栈维护

下凸壳，目标斜率递减；上凸壳，目标斜率递增

使用单调栈维护，因为我们移出一个点时只会从一个方向移出，就相当于一个单调栈

同上

cpp
1
2
3
4
5
6
#define st sta[sta.size()-1]
#define nd sta[sta.size()-2]
while(sta.size()>=2&&slope(st,nd)<目标斜率) sta.pop_back();
dp[i]=...通过sta[st]进行转移
while(sta.size()>=2&&slope(st,i)>slope(st,nd)) sta.pop_back();
sta.push_back(i);

二分凸包

当目标斜率并没有单调性时，我们就不能随意的移出凸包上的点。我们需要维护整个凸包。通过二分来查找最优决策点

cpp
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int get(int k){
	if(tail==head) return que[head];
	int l=head,r=tail,mid,ans;
	while(l<=r){
		mid=(l+r)>>1;
		if(slope(que[mid],que[mid+1])<=k)){
			ans=mid;
			r=mid-1;
		}else{
			l=mid+1;
		}
	} 
	return ans;
}

转移并维护凸包

cpp
1
2
3
4
int p=get(目标斜率);
dp[i]=...通过p进行转移
while(head<tail&&slope(que[tail],que[tail-1])>slope(que[tail],i)) tail--;
que[++tail]=i;

splay维护

上述情况，决策点的横坐标总是单调递增的。但如果决策点横坐标没有单调性，则需要splay来动态维护凸包。其他还有CDQ分治和set维护动态凸包，未完待续...

二维状态

二维状态下的斜率优化和一维状态的情况类似。对于状态 $dp[x][k]$ ，其由 $dp[1...x][k-1]$ 转移过来，则可以看做一个滚动数组。

首先最外层循环k，每次循环时，将单调队列清空，注意单调队列初始化方法

cpp
1
2
head=tail=1;
que[head]=0;

其余类似于一维情况

注意单调队列维护的是 $dp[..][k-1]$ 中的决策点。换句话说，$[k]$ 这一层dp的结果并不会作为这一层之后dp时的决策点，而是作为 $[k+1]$ 层的决策点。全部的决策点已经在这一层开始dp之前求好了，就差这一层dp时进行维护

有限制的转移

以P5504 [JSOI2011] 柠檬为例，本题转移时，要求决策点j还要满足 $s[i]=s[j]$ 的条件。我们可以将不同类的决策点放入不同的单调队列/单调栈中，dp时从满足条件的集合中选取

cpp
1
2
3
4
5
6
7
vector<int> sta[100004];
#define st sta[now][sta[now].size()-1]
#define nd sta[now][sta[now].size()-2]
for(int i=1;i<=n;i++){
	int now=s[i];
	.... 
}

值得注意的时，本题中dp到i时，i本身也可以作为一个决策点，毕竟转移方程是 $dp[i]=dp[j-1]...（j可以为i）$

所以可以先加入决策点i，再选取决策点，把两个while换一下位置

精度问题

精度问题在二分凸包的类型中会凸显重要性
斜率用double类型表示难免会造成精度损失，因此在比较斜率时，可以把分数展开，用乘法形式，例如：

cpp
1
while(sta[now].size()>=2&&(Y(i)-Y(st))*(X(st)-X(nd))>(Y(st)-Y(nd))*(X(i)-X(st))) sta[now].pop_back();

此时，不等号取登也有了意义，可以对不等号取等

cpp
1
while(sta[now].size()>=2&&(Y(i)-Y(st))*(X(st)-X(nd))>=(Y(st)-Y(nd))*(X(i)-X(st))) sta[now].pop_back();

另外，需要根据单调性，确保 $(Y(i)-Y(st))$ 等是正的