[DP淺析]線性DP初步 – 2 – 單調隊列優化
#0.0 前置知識
本文為單調隊列優化dp，請確保你已熟練掌握以下知識：
#1.0 簡單介紹
#1.1 本質 & 適用範圍
運用單調隊列優化dp，本質是利用單調性，及時排除不可能的決策，以保持候選集合的有效性和秩序性。
單調隊列非常適合優化決策取值範圍的上、下界均單調變化，每個決策在候選集合中插入或刪除至多一次
#1.2 適用方程 & 條件
可以使用單調隊列的狀態轉移方程大多可歸為如下形式：
f_i=\min_{L(i)\leq j\leq R(i)}\{f_j+val(i,j)\}
\end{aligned}
\]
其中 \(L(i)\) 和 \(R(i)\) 是兩個關於 \(i\) 的一次函數，限制了 \(j\) 的取值範圍，\(val(i,j)\) 是一個關於 \(i,j\) 的多項式函數。
條件：
- 多項式 \(val(i,j)\) 的每一項僅與 \(i\) 和 \(j\) 中的一個有關
直接上例題
#2.0 例題講解
#2.1 P3572 [POI2014]PTA-Little Bird
#2.1.1 關於題面
題面的翻譯少給了很重要的一句：
小鳥從第一棵樹開始跳躍 (On top of the first one, there is a little bird who …)
#2.1.2 樸素演算法
相信不難寫出本題的狀態轉移方程：
f_i = \min_{i-k\leq j<i}\{f_j+[a_j\leq a_i]\}
\end{aligned}
\]
偽程式碼：
&f_1 \leftarrow 0\\
&\text{For }i \leftarrow2\text{ to }n\\
&\quad\quad \text{do For }j\leftarrow i-k\text{ to }i-1\text{ by }1\text{ do}\\
&\quad\quad\quad\quad f_i\leftarrow\min\{f_i,f_j+(a_j<=a_i)\ ?\ 1:0\}\\
&\quad\quad \text{End}
\end{aligned}
\]
#2.1.3 單調性分析
觀察 \(j\) 的取值範圍：
i-k\leq j<i
\end{aligned}
\]
當 \(i\) 增加 \(1\) 時，\(j\) 的範圍的上界與下界均增加 \(1\)，也就意味著每次只有一個新的決策 \(f_i\) 加入候選集合，最多一個舊的決策 \(f_{i-k}\) 被排除候選集合，顯然，候選集合中下標應是單調遞增的，這一點無需格外關注
顯然，我們希望每一次得到的決策 \(f_j\) 應該是候選集合中最小的，也就是說，如果有決策 \(f_p,f_q,p<q<i,f_p>f_q\) ，顯然 \(f_q\) 比 \(f_p\) 更優，因為 \(f_q\) 比 \(f_p\) 在候選集合中可持續的時間更長，且貢獻的 \(f\) 值更小，那麼 \(f_p\) 顯然是無用的，可以直接放棄，因此，我們應該維護候選集合中 \(f_j\) 單調遞增
那如果 \(f_p=f_q\) 呢？顯然我們選高度更高的，即 \(a\) 更大的更優
- 因為假設 \(a_p<a_q\)
- 如果 \(a_p<a_q\leq a_i\) ，兩者都需要加一，所以兩者的貢獻是相同的，而 \(p<q\)，這意味著 \(q\) 可以在隊列中保存更長時間，那麼選 \(p\) 顯然就可以直接丟棄
- 若 \(a_p\leq a_i<a_q\)，顯然選擇 \(a_q\) 得到的結果更優
- 若 \(a_i<a_p<a_q\)，無論選 \(p\) 還是 \(q\) 得到的結果都相同，而 \(p<q\)，這意味著 \(q\) 可以在隊列中保存更長時間，那麼選 \(p\) 顯然就可以直接丟棄
- 若 \(a_p=a_q\)，顯然無論如何 \(p\) 與 \(q\) 的貢獻都是相同的， \(p<q\)，這意味著 \(q\) 可以在隊列中保存更長時間，那麼選 \(p\) 顯然就可以直接丟棄
- 但是，如果 \(a_p>a_q\)，\(a_q\) 仍然有可能是後面轉移的最優決策（當 \(p\) 已經超出範圍時，\(q\) 仍然有可能在範圍內且是最優決策）
所以應維護候選集合中當 \(f_j\) 相等時， \(a_j\) 單調遞減
綜合以上的結論，決策的選擇是存在單調性的，我們可以維護一個如下的單調隊列
- \(f_j\) 單調遞增
- 當 \(f_j\) 相等時， \(a_j\) 單調遞減
#2.1.4 碼程式碼
const int N = 1000010;
const int INF = 0x3fffffff;
int n,k,t,a[N],f[N],q[N];
int main(){
scanf("%d",&n);
for (int i = 1;i <= n;i ++)
scanf("%d",&a[i]);
scanf("%d",&t);
while (t --){
scanf("%d",&k);
int frt = 0,tal = -1; //清空隊列
q[++ tal] = 1; //加入初始候選決策
for (int i = 2;i <= n;i ++){
while (frt <= tal && q[frt] + k < i)
frt ++; //去掉超出範圍的
f[i] = f[q[frt]] + (a[q[frt]] <= a[i]); //轉移
while (frt <= tal && ((f[q[tal]] > f[i]) || (f[q[tal]] == f[i] && a[q[tal]] <= a[i])))
tal --; //從隊尾維護單調性,將新決策入隊
q[++ tal] = i;
}
cout << f[n] << endl;
}
return 0;
}
#2.2 P3089 [USACO13NOV]Pogo-Cow S
#2.2.1 樸素演算法
首先，不難想到，最大得分一定是從一端開始，一直向一個方向跳躍，所以我們上來就需要一個 sort() 對數據進行排序，又因為有兩個方向，所以要進行兩次DP
設 \(f_{i,j}\) 表示最後一步從 \(j\) 到 \(i\) 的最大得分
不難寫出轉移方程：
f_{i,j} = \max_{k<j<i\and x_j-x_k\leq x_i-x_j}\{f_{j,k}\}+p_i
\end{aligned}
\]
程式碼：
const int N = 1010;
const int INF = 0x3fffffff;
struct Node{
int p;
int a;
};
Node s[N];
int n,sum[N],f[N][N],ans;
int cmp(const Node x,const Node y){
return x.p < y.p;
}
int main(){
scanf("%d",&n);
for (int i = 1;i <= n;i ++)
scanf("%d%d",&s[i].p,&s[i].a);
sort(s + 1,s + n + 1,cmp);
for (int i = 1;i <= n;i ++)
f[i][i] = s[i].a;
for (int i = 1;i <= n;i ++)
for (int j = 1;j < i;j ++){
for (int k = 1;k <= j;k ++)
if (s[j].p - s[k].p <= s[i].p - s[j].p)
f[i][j] = max(f[i][j],f[j][k] + s[i].a);
ans = max(ans,f[i][j]);
}
mset(f,0);
for (int i = 1;i <= n;i ++)
f[i][i] = s[i].a;
for (int i = n;i >= 1;i --)
for (int j = n;j > i;j --){
for (int k = n;k >= j;k --)
if (s[k].p - s[j].p <= s[j].p - s[i].p)
f[i][j] = max(f[i][j],f[j][k] + s[i].a);
ans = max(ans,f[i][j]);
}
cout << ans;
return 0;
}
#2.2.2 單調性分析
觀察轉移方程
f_{i,j} = \boxed{\max_{k<j<i\and x_j-x_k\leq x_i-x_j}\{f_{j,k}\}}+p_i
\end{aligned}
\]
加框的部分是在求 \(f_{j,k}\) 的最大值，考慮可不可以採用單調性優化，不難發現，數列 \(\{x_k\}\) 本身便是一個具有單調性的數列，當 \(j\) 不變時，\(i\) 增加一，轉移方程為
f_{i+1,j} = \max_{k<j<i+1\and x_j-x_k\leq x_{i+1}-x_j}\{f_{j,k}\}+p_{i+1}
\end{aligned}
\]
\(k\) 的取值範圍 \(1\leq k<j\) 沒有變化，只是滿足 \(x_j-x_k\leq x_{i+1}-x_j\) 的 \(k\) 可能增多了，而且，顯然若 \(x_j-x_p\nleq x_{i+1}-x_j\)，對於 \(q<p\) 則必然有 \(x_j-x_q\nleq x_{i+1}-x_j\)，這就相當於直接存在一個不需要出隊的單調隊列，因為數列 \(\{x_k\}\) 本身便是一個具有單調性的數列，我們只需記錄下當前滿足 \(x_j-x_k\leq x_{i+1}-x_j\) 的最小的 \(k\)，保存該區間內最大值，下一次從 \(k+1\) 開始更新即可，注意，由於這裡是 \(i\) 增加一，\(j\) 不變的情況，所以要將 \(j\) 的變化放在外層循環，\(i\) 在內層
#2.2.3 碼程式碼
const int N = 1010;
const int INF = 0x3fffffff;
struct Node{
int p;
int a;
};
Node s[N];
int n,sum[N],f[N][N];
int cmp(const Node x,const Node y){
return x.p < y.p;
}
int main(){
scanf("%d",&n);
for (int i = 1;i <= n;i ++)
scanf("%d%d",&s[i].p,&s[i].a);
sort(s + 1,s + n + 1,cmp);
int ans = 0;
for (int j = 1;j < n;j ++){
int k = j;
f[j][j] = s[j].a;
for (int i = j + 1;i <= n;i ++){
f[i][j] = f[i - 1][j] - s[i - 1].a; //顯然上一次轉移的值必然是上個區間最大值
while (k && s[j].p - s[k].p <= s[i].p - s[j].p)
f[i][j] = max(f[i][j],f[j][k --]);
f[i][j] += s[i].a;
ans = max(ans,f[i][j]);
}
}
mset(f,0);
for (int j = n;j > 1;j --){ //別忘了求兩次，順序反過來
int k = j;
f[j][j] = s[j].a;
for (int i = j - 1;i >= 1;i --){
f[i][j] = f[i + 1][j] - s[i + 1].a;
while (k <= n && s[k].p - s[j].p <= s[j].p - s[i].p)
f[i][j] = max(f[i][j],f[j][k ++]);
f[i][j] += s[i].a;
ans = max(ans,f[i][j]);
}
}
cout << ans;
return 0;
}
#3.0 單調隊列優化多重背包
#3.1 分析
我們先來考慮最樸素的多重背包問題解法
狀態轉移方程為
f_j=\max_{1\leq cnt \leq c_i}\{f_{j-cnt\times v_i}+cnt\times W_i\}
\end{aligned}
\]
偽程式碼：
&\text{For }i\leftarrow1\text{ to }n\\
&\quad\quad \text{do For }cnt\leftarrow 1\text{ to }c_i\\
&\quad\quad\quad\quad \text{do For }j\leftarrow M\text{ to }cnt\times v_i\text{ by }-1\text{ do}\\
&\quad\quad\quad\quad\quad\quad f_{j}\leftarrow\max\{f_j,f_{j-cnt\times v_i}+cnt\times w_i\}\\
&\quad\quad\quad\quad\text{End}
\end{aligned}
\]
我們來看一下能夠轉移到狀態 \(j\) 的決策候選集合，為 \(\{j-cnt\times v_i|1\leq cnt\leq c_i\}\)
再看一下能夠轉移到 \(j-1\) 的候選集合，為 \(\{j-cnt\times v_i-1|1\leq cnt\leq c_i\}\)
顯然這兩個集合沒有交集，無法快速地從 \(j\) 的決策集合轉移到 \(j-1\) 的決策集合
那麼，我們從最內層循環向外一層，觀察 \(cnt\) 對 \(j\) 的決策集合的影響
當 \(cnt\) 加一時，狀態 \(j-v_i\) 的決策候選集合為 \(\{j-(cnt+1)\times v_i|1\leq cnt+1\leq c_i\}\)
如下圖：
顯然，如果我們把狀態 \(j\) 按照按照以模 \(v_i\) 的餘數 \(u\) 分組，令 \(p\in[0,\lfloor\dfrac{M-u}{v_i}\rfloor]\)，倒序循環，每一組的決策候選集合是可以快速推出的，新的狀態轉移方程：
f_{u+p\times v_i}&=\max_{p-c_i\leq k\leq p-1}\{f_{u+k\times v_i}+(p-k)\times w_i\}\\
&=\max_{p-c_i\leq k\leq p-1}\{f_{u+k\times v_i}-k\times w_i+p\times w_i\}
\end{aligned}
\]
顯然，如果我們想要得到的結果儘可能大，就需要決策 \(k\) 的 \(f_{u+k\times v_i}-k\times w_i\) 儘可能大
那麼當 \(p\) 減小一時，\(k\) 的取值範圍上下界均減小一，我們需要一個 \(k\) 單調遞減，\(f_{u+k\times v_i}-k\times w_i\) 單調遞減的單調隊列，每次按照單調隊列的基本操作進行維護即可
#3.2 碼程式碼
const int N = 100010;
const int INF = 0x3fffffff;
int n,m;
int v[N],w[N],c[N];
int f[N],q[N];
inline int val(int i,int u,int k){
return f[u + k * v[i]] - k * w[i];
}
int main(){
scanf("%d%d",&n,&m);
for (int i = 1;i <= n;i ++){
scanf("%d%d%d",&w[i],&v[i],&c[i]);
for (int u = 0;u < v[i];u ++){
int l = 0,r = -1;
int maxp = (m - u) / v[i];
for (int k = maxp - 1;k >= max(maxp - c[i],0);k --){
while (l <= r && val(i,u,q[r]) <= val(i,u,k))
r --;
q[++ r] = k;
}
for (int p = maxp;p >= 0;p --){
while (l <= r && q[l] > p - 1)
l ++;
if (l <= r)
f[u + p * v[i]] = max(f[u + p * v[i]],val(i,u,q[l]) + p * w[i]);
if (p - c[i] - 1 >= 0){
while (l <= r && val(i,u,q[r]) <= val(i,u,p - c[i] - 1))
r --;
q[++ r] = p - c[i] - 1;
}
}
}
}
int ans = 0;
for (int i = 0;i <= m;i ++)
ans = max(ans,f[i]);
cout << ans;
return 0;
}
