動態規劃
動態規劃是把一類具有相同點的狀態的一起處理，極大優化搜索。
dp復雜度一般\(≥O(狀態數)\)。
1.基礎知識
1.1.解題思路
先設計好樸素的dp方程，列出狀態表示→從“最后一步”考慮狀態轉移，若不能轉移，考慮從“最后一步”和題目關鍵元素或限制補充狀態表示→再從狀態、轉移上考慮優化，或者對原來的dp方程進行等價變形（\(e.g.\)所有第i層狀態由第i-1層的某個狀態轉移過來，則可省略第i維。第i層的每個狀態都由第i-1層的所有狀態轉移過來，則可省略除第i維外的所有維度）
1.2.閻氏dp分析法——從集合的角度思考問題
集合劃分依據（重要）：1.別人推自己：“最后”：當前的狀態是由哪個狀態通過最后一步轉移過來的；2.自己推別人：一個已知狀態應該更新哪些后序階段的未知狀態。
集合劃分原則：1.不遺漏。2.不重復（僅對集合屬性是方案數有此要求）。
1.3.dp的實現方式
- 若dp的轉移是DAG：保證用到當前狀態時在DAG上所有該狀態的入邊已經轉移完全。
- 若dp的轉移有環：環形dp處理、分層圖跑dijkstra或spfa、高斯消元……。
一般采用遞推枚舉dp的轉移順序。
若不能直接遞推枚舉dp的轉移順序：記憶化搜索、分層圖跑dijkstra或spfa、dp套dp……。
1.3.1.遞推實現
for(int i=1;i<=n;i++) f[i]=f[i-1];
1.3.2.遞歸實現——記憶化搜索
適用條件：
-
會重復遍歷某個狀態。
- 網格圖上下左右走。
- 圖。
降低復雜度為\(O(狀態數)\)。
-
遞推循環層數多。
int dp(int x)
{
int &v=f[x];//注意別寫錯成int v=&f[x];
if(v>=0) return v;//不要寫v!=-1，因為-nan!=-1也為真會返回-nan！??！
//abaabaaba
v=dp(v);
return v;
}
memset(f,-1,sizeof(f));
for(int i=1;i<=n;i++) dp(i);
1.4.dp求具體方案
1.4.1.路徑追蹤
\(pre[i][...]\)：f[i][...]是由pre[i][...]轉移而來的。
若轉移的狀態只有1個（\(e.g.\)\(f[i][...]=\max\limits_{j=1}^{i-1}f[j][...]\)，\(f[i][...]\)是由\(f[j][...],j\in[1,i-1]\)其中的一個轉移而來），則pre[i][...]是一個struct（記錄狀態的所有維度以及決策）數組。在轉移過程中，一旦當前的轉移條件成立時，記錄從哪個狀態轉移而來。（\(e.g.\)最值轉移中只要當前最值條件成立，當前先記錄從哪個狀態轉移而來，如果后面出現更優的轉移，則之前的記錄會被覆蓋）
若轉移的狀態有多個，則pre[i][...]是一個vector。在轉移過程中，記錄所有合法轉移而來的狀態。
執行完dp后從目標狀態進行倒推，采用記憶化搜索，倒推路徑是pre[i][...]，記錄決策。
1.4.2.狀態倒推
適用條件：路徑追蹤的方法不適用或MLE時。
從目標狀態倒推回初始狀態的整個轉移路徑，如果出現某一狀態等于另一個狀態的轉移，則記錄這個決策為方案的一部分。
\(e.g.\)《動態規劃2.3.10. 背包問題求具體方案 》
1.5.費用提前計算思想
當a→b的轉移的費用為x+y，其中費用y會累加到b→...的轉移的費用，且題目只關心最后的費用時，令a→b中狀態b的費用=x+后面狀態的數量*y。
1.6.啟示
-
動態規劃是全局視野的。dp要計算當前狀態的所有值把握全局。
\(e.g.\)關路燈：走到一個路燈計算一個路燈的耗電量是眼界狹隘的，應該走一步計算所有路燈的耗電變化量把握全局。
-
狀態計算時，最重要的是集合劃分，即狀態之間最后一個不同點。e.g.AcWing 280.陪審團講解視頻
-
推理狀態轉移方程時，要看幾個狀態間什么是不變的（相同的），什么是變化的（不同的）。e.g.AcWing 280.陪審團講解視頻
-
循環順序：階段 -> 狀態 -> 決策
-
如果f[]中不包含某個信息，就不必考慮該信息的后效性。e.g.AcWing 312.烏龜棋
-
有時可以通過額外的算法確定dp的計算順序。e.g.預處理貪心排序。
-
數據結構優化dp：多維dp在執行內部循環時，把外部循環變量看作定值。狀態轉移取最優決策時，簡單的限制條件用循環順序處理，復雜的用數據結構維護。
-
f[i][j]：把j放在內層循環常數會小。
-
把二元項拆成一元項，可以方便后面優化。
-
環形dp中，兩點之間的路徑有2條，對于一個點可以通過距離限定另一個點的選擇范圍強制令兩點之間的路徑只有一條。
-
對于“區間類”線性dp（\(e.g.\)\(\forall i\in[1,n],f[r[i]]=\max\{ f[l[i]-1] \}+(r[i]-l[i]+1)\)）,把每個區間的左端點存在右端點的vector用于轉移。
-
\(f_{i,j}←f_{i-1,?}\Rightarrow f_{i,j}←f_{i,j-1}\)，有時會有意想不到的優化。
\(e.g.\)一個\(O(N)\)轉移的式子\(f[i][j]=\sum\limits_{k=0}^j (f[i-1][k]*a^{j-k}*b)\)。
把j-1代入得：\(f[i][j-1]=\sum\limits_{k=0}^{j-1} (f[i-1][k]*a^{j-1-k}*b)\)。
所以\(f[i][j]=f[i][j-1]*a+f[i-1][j]*b\)。由此做到\(O(1)\)轉移。
-
當前視野較難推知到全局視野：從全局逆推：\(f[i]\)：從i到終點的……。記憶化搜索。
2.線性dp
2.1.路徑取數模型
特征：路徑最值問題。
2.1.1.數字三角形
\(f[i][j]\)：從(1,1)走到(i,j)的所有方案中，路徑上的數字的和最大是多少。
狀態轉移：\(f[i][j]=\max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j])\)：分別表示從左上角和上方最后一步走到(i,j)。
邊界：\(f[1][1]=a[1][1]\)。另外轉移時不能越過三角形的界限。
目標：\(\max\limits_{1≤j≤N} \{ f[N,j] \}\)。
int n,ans=-INF;
int a[N][N]; //數字三角形
int f[N][N]; //f[i][j]：從(1,1)走到(i,j)的所有方案中，路徑上的數字的和最大是多少
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=i;j++)
scanf("%d",&a[i][j]);
memset(f,0,sizeof f);
f[1][1]=a[1][1];
for(int i=2;i<=n;i++)
for(int j=1;j<=i;j++)
f[i][j]=max(f[i-1][j-1]+a[i][j],f[i-1][j]+a[i][j]);
for(int j=1;j<=n;j++) ans=max(ans,f[n][j]);
printf("%d\n",ans);
2.1.2.矩陣取數
具體狀態表示及轉移見代碼。
- 例題1：1取矩陣數
int a[N][N]; //方格數
int f[N][N]; //f[i][j]：從(1,1)走到(i,j)的所有方案中，路徑上的數字的和最大是多少
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
scanf("%d",&a[i][j]);
memset(f,0,sizeof f);
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
f[i][j]=max(f[i][j-1],f[i-1][j])+a[i][j];
printf("%d\n",f[n][m]);
- 例題2：2取矩陣數
int w[N][N]；
int f[N*2][N][N]; //f[k][i][j]：2條路線同時走了k步，一條目前位于(i,k-i)，另一條(j,k-j)
scanf("%d%d",&m,&n);
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
scanf("%d",&w[i][j]);
for(int k=1+1;k<=m+n;k++) //從(1,1)到(m,n)
for(int i=1;i<=m && k-i>=1;i++)
for(int j=1;j<=m && k-j>=1;j++){
/*
f[k-1][i][...] -> f[k][i][...]表示從(i,(k-1)-i)即（(i,k-i-1)）走到(i,k-i)，即向右走
f[k-1][i-1][...] -> f[k][i][...]表示從(i-1,(k-1)-(i-1))即（(i-1,k-i)）走到(i,k-i)，即向下走
*/
f[k][i][j]=max(f[k][i][j],f[k-1][i-1][j-1]);
f[k][i][j]=max(f[k][i][j],f[k-1][i-1][j]);
f[k][i][j]=max(f[k][i][j],f[k-1][i][j-1]);
f[k][i][j]=max(f[k][i][j],f[k-1][i][j]);
f[k][i][j]+=w[i][k-i];
if(i!=j) f[k][i][j]+=w[j][k-j]; //不能重復增加好感度
}
printf("%d\n",f[m+n][m][m]);、
-
例題3：k取矩陣數
《圖論.4..建圖應用》
2.2.最長上升子序列模型
特征：序列最值問題（序列中的數會相互影響，含有偏序關系）。
計算當前節點時，先轉移求最值，再加上自己的信息。
2.2.1.最長上升子序列模型\(O(N^2)\)
\(f[i]\):所有以a[i]為結尾的“最長上升子序列”的最大長度。
狀態轉移：\(f[i]=\max\limits_{0≤j<i,a[j]<a[i]} \{ f[j] \}+1\)。
邊界：\(f[i]=1\)，只有a[i]一個數。
目標：\(\max\limits_{1≤i≤N} \{ f[i] \}\)。
int a[N];//序列
int f[N];
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
f[i]=1;
for(int j=1;j<i;j++) if(a[j]<a[i]) f[i]=max(f[i],f[j]+1);
}
for(int i=1;i<=n;i++) ans=max(ans,f[i]);
printf("%d\n",ans);
2.2.2.應用
具體狀態表示及轉移見代碼。
-
例題1：最長上升子序列\(O(N \log N)\)
二分查找在q中找>=a[i]的數中最小的一個，不存在返回len+1。
大數往后面填，小數覆蓋前面。
int a[N]; //序列
int q[N],len; //最長上升子序列
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++)
{
int l=1,r=len+1; //len+1：給大數留個空
while(l<r) //在q中找>=a[i]的數中最小的一個，不存在返回len+1
{
int mid=(l+r)>>1;
if(q[mid]<a[i]) l=mid+1;
else r=mid;
}
len=max(len,r); //如果a[i]是大數二分返回len+1，更新答案
q[r]=a[i]; //大數往后面填，小數覆蓋前面
}
printf("%d\n",len);
- 例題2：最長公共子序列
char a[N],b[N];
int f[N][N]; //f[i][j]：前綴子串a[1~i]與b[1~j]的“最長公共子序列”的長度
scanf("%d%d",&n,&m);
scanf("%s%s",a+1,b+1);
//邊界：f[i,0]=f[0,j]=0
for(int i=1;i<=n;i++)
for(int j=1;j<=m;j++)
{
f[i][j]=max(f[i-1][j],f[i][j-1]);
if(a[i]==b[j]) f[i][j]=max(f[i][j],f[i-1][j-1]+1);
}
printf("%d\n",f[n][m]);
-
例題3：最長先升后降子序列
最長先升后降子序列=從前往后遞推的最長上升子序列+從后往前遞推的最長下降子序列-公共交點。
int f[N],g[N]; //從前往后遞推的最長上升子序列和從后往前遞推的最長下降子序列
for(int i=1;i<=n;i++)
{
f[i]=1;
for(int j=1;j<i;j++) if(a[j]<a[i]) f[i]=max(f[i],f[j]+1);
}
for(int i=n;i>=1;i--)
{
g[i]=1;
for(int j=n;j>i;j--) if(a[i]>a[j]) g[i]=max(g[i],g[j]+1);
}
for(int i=1;i<=n;i++) ans=max(ans,f[i]+g[i]-1); //還要減去公共交點i
printf("%d\n",ans);
-
例題4：最大上升子序列和
求一個序列所有上升子序列中子序列和的最大值。
只需把最長上升子序列模型更改一下計算貢獻的方式即可。
for(int i=1;i<=n;i++)
{
f[i]=a[i];
for(int j=1;j<i;j++) if(a[j]<a[i]) f[i]=max(f[i],f[j]+a[i]);
}
-
例題5：最長公共上升子序列
對于兩個數列 A 和 B，如果它們都包含一段位置不一定連續的數，且數值是嚴格遞增的，那么稱這一段數是兩個數列的公共上升子序列，而所有的公共上升子序列中最長的就是最長公共上升子序列了。求最長公共上升子序列的長度。
int n,ans;
int a[N],b[N];
int f[N][N];
int main(){
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
for(int i=1;i<=n;i++) scanf("%d",&b[i]);
for(int i=1;i<=n;i++){
int ma=1;
for(int j=1;j<=n;j++){
f[i][j]=f[i-1][j];
if(a[i]==b[j]) f[i][j]=max(f[i][j],ma);
if(a[i]>b[j]) ma=max(ma,f[i-1][j]+1);
}
}
for(int i=1;i<=n;i++) ans=max(ans,f[n][i]);
printf("%d\n",ans);
return 0;
}
-
例題6：求序列\(A\)長度為\(M\)的嚴格遞增子序列的個數
求序列\(A\)長度為\(M\)的嚴格遞增子序列的個數。
\(f[i][j]\)：前\(j\)個數以\(A_j\)結尾的數列，長度為\(i\)的嚴格遞增子序列有多少個（\(i\)、\(j\)均可作階段）。
特殊地，令\(A_0=-INF\)。
狀態轉移方程
const int INF=1<<30,MOD=1e9+7;
memset(f,0,sizeof f);
a[0]=-INF;
f[0][0]=1;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
for(int k=0;k<j;k++)
if(a[k]<a[j]) f[i][j]=(f[i][j]+f[i-1][k])%MOD;
int ans=0;
for(int i=1;i<=n;i++) ans=(ans+f[m][i])%MOD;
數據結構優化
樹狀數組維護前綴和。
在序列A（不包括\(A_0\)）中的數值的值域上建立樹狀數組。
把外層循環i看作定值。當j增加1時，k的取值范圍從0≤k<j變為0≤k<j+1，也就是多了一個k=j新決策。
設一個決策\((A_k,f[i-1,k])\)。
- 插入一個新決策。在j增加1前，把\((A_j,f[i-1,j])\)插入集合：把\(A_k\)上的位置的值增加\(f[i-1,k]\)。
- 給定一個值\(A_j\)，查詢滿足\(A_k<A_j\)的二元組對應的\(f[i-1,j]\)的和：在樹狀數組計算\([1,A_j-1]\)的前綴和。
//樹狀數組維護前綴和
#include<bits/stdc++.h>
using namespace std;
const int N=1005,MOD=1e9+7;
int t,n,m,ans;
int a[N],f[N][N]; //f[i][j]：前i個數以Aj結尾的數列，長度為j的嚴格遞增子序列有多少個（i、j均可作階段）
int nums[N],cnt; //離散化
int tr[N]; //樹狀數組維護前綴和
inline int lowbit(int x){
return x&-x;
}
void add(int x,int v){
while(x<=cnt){
tr[x]=(tr[x]+v)%MOD;
x+=lowbit(x);
}
return ;
}
int sum(int x){
int res=0;
while(x>0){
res=(res+tr[x])%MOD;
x-=lowbit(x);
}
return res;
}
int main(){
scanf("%d",&t);
for(int C=1;C<=t;C++){
ans=0;
scanf("%d%d",&n,&m);
cnt=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
nums[++cnt]=a[i];
}
//離散化
sort(nums+1,nums+cnt+1);
cnt=unique(nums+1,nums+cnt+1)-nums-1; //注意這里要-1
for(int i=1;i<=n;i++) a[i]=lower_bound(nums+1,nums+cnt+1,a[i])-nums+1;
for(int i=1;i<=n;i++) f[i][1]=1;
for(int j=2;j<=m;j++){
for(int i=1;i<=cnt;i++) tr[i]=0;
for(int i=1;i<=n;i++){
f[i][j]=sum(a[i]-1);
add(a[i],f[i][j-1]);
}
}
for(int i=1;i<=n;i++) ans=(ans+f[i][m])%MOD;
printf("Case #%d: %d\n",C,ans);
}
return 0;
}
-
例題7：求序列\(A\)長度大于等于2且滿足\(\forall i,C_{a_i}^{a_{i+1}}\)是奇數的不上升子序列的個數
保證1≤n≤211985，1≤a_i≤233333。所有的a_i互不相同。原題鏈接。
\(C_{a_i}^{a_{i+1}}\)是奇數\(\Leftrightarrow\)\(C_{a_i}^{a_{i+1}}\bmod 2=1\)。
即盧卡斯拆位過程中不能出現\(C_0^1\)。
也就是說\(C_n^m\)中二進制下不存在某一位n為0而m為1，即二進制下m是n的子集。
問題就變成了求子序列的個數，滿足每一項在二進制下是前一項的子集。而且既然都是前一項的子集了，序列也一定是不上升的
又因為a≤233333還互不相同，所以直接設\(f[i]\)：以權值i結尾的合法子序列個數。枚舉子集從自己轉移給別人。
- 把一個序列A變成非嚴格單調遞增的，至少需要修改 序列總長度-A的最長不下降子序列長度 個數。
- 把一個序列A變成嚴格單調遞增的，至少需要修改 構造序列B[i]=A[i]-i，序列總長度-B的最長不下降子序列長度 個數。
- 把一個序列A變成嚴格單調的，至少需要花費多少偏移量？
- 給定一個序列A，可以選擇一個區間 [l,r]，使下標在這個區間內的數都加一或者都減一，至少要修改 差分后的序列\(**\max(\sum|所有正數|,\sum|所有負數|)**\)$ \(次，且可以得到不同的序列\) |\sum|所有正數|-\sum|所有負數||+1$ 種。
- 求序列A的最大連續子段和：O(N)掃描該數列，不斷把新的數加入子段，當子段和變成負數時，把當前的整個子段清空。掃描過程中出現過的最大子段和即為所求。
- Dilworth 定理（“覆蓋”與“最值”的轉換思想）：最長上升子序列的長度=最小的用不上升子序列覆蓋序列的子序列個數。
2.3.背包模型
特征：組合類最值問題（預選范圍內的元素不會互相影響）。
背包的瓶頸在于體積，它是NPC問題。因此當題目的體積很大時，考慮題目中的特殊條件。
- 生成函數。
2.3.1.基礎知識
循環順序：階段 -> 狀態 -> 決策。
| | | ... | |
————————————————————————————————————————————————————》
體積 r r+v r+2v ... j-v j
01背包
求所有前綴的最大值，故用一個變量維護就夠了。
f[i][j]=max(f[i-1][j],f[i-1][j-v]+wi);
如果省略第i維，采用j正序循環，在更新f[i][j]前，f[i-1][j-v]已經被f[i][j-v]覆蓋，但是j倒序循環就沒有這個問題。故可用一維數組優化，j倒序循環。（如果用滾動數組優化，j正序循環）
完全背包
求所有前綴的最大值，故用一個變量維護就夠了。
f[i][j]=max(f[i-1][j],f[i][j-v]+wi);
如果省略第i維，在更新f[i][j]前，可以保證f[i-1][j]和f[i][j-v]沒有被覆蓋，故可用一維數組優化，j正序循環。
多重背包
求滑動窗口的最大值，故要用單調隊列維護。
f[i][j]=max(f[i-1][j],f[i-1][j-v]+wi,f[i-1][j-2v]+2wi,...,f[i-1][j-siv]+siwi);
如果省略第i維，采用j正序循環，在更新f[i][j]前，f[i-1][j-nv]已經被f[i][j-nv]覆蓋，且由于要配合單調隊列j不能倒序循環，故只可用滾動數組優化，j正序循環。
2.3.2. 01背包 時間\(O(NM)\) 空間\(O(M)\)
每個物品可被選一次或不被選。
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m;
int v[N],w[N];
int f[N]; //f[j]：背包中放入總體積不超過j的物品的最大價值和（物品的體積和<=j）
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);
/*如果要求物品的體積和恰好等于j，則加上：
memset(f,-0x3f,sizeof f);
f[0]=0;
*/
for(int i=1;i<=n;i++)
for(int j=m;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+w[i]);
printf("%d\n",f[m]);
return 0;
}
2.3.2.1.應用
例題1
給定n(n≤100)個區間\([l_i,r_i]\)(\(0≤l_i≤r_i≤10^3,l\in Z\))和一個實數x，第i個區間可以在\([l_i,r_i]\)的范圍內選1個數或者不選，求選出的數的總和在不超過x的情況下與x的差值的最小值。
選擇1個區間，至少增加\(l_i\)的下界，并且還有\(len_i=r_i-l_i\)的“伸縮量”。
記l=增加量下界，len_l=增加量下界為l時所對應的某個伸縮量。
\(ans=min\{x,\max\limits_{l=0}^{x} \{l+len_l\} \}\)。
那么對于每一個下界，其伸縮量越大越好。所以可以考慮動態規劃。
f[i]：下界和為i的情況下的最大伸縮量。恰好下界保證是非負整數。
邊界：f[0]=0，其他均為?∞。
轉移：每個區間選或者不選，顯然是01背包去做。把l[i]看作體積，len[i]看作價值。
\(ans=min\{x,\max\limits_{i=0}^{x} \{i+f[i]\} \}\)。
注意到數據范圍\(l_i≤250\)，記\(fup=\sum\limits_{i=1}^n l_i\)，dp第一維的上界是min(x,fup)。
2.3.3. 完全背包 時間\(O(NM)\) 空間\(O(M)\)
每個物品可被選任意次。
#include<bits/stdc++.h>
using namespace std;
const int N=1005,INF=0x3f3f3f3f;
int n,m,ans=-INF;
int v[N],w[N];
int f[N]; //f[j]：背包中放入總體積不超過j的物品的最大價值和
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);
/*如果要求物品的體積和恰好等于j，則加上：
memset(f,-0x3f,sizeof f);
f[0]=0;
*/
for(int i=1;i<=n;i++)
for(int j=v[i];j<=m;j++)
f[j]=max(f[j],f[j-v[i]]+w[i]);
for(int j=1;j<=m;j++) ans=max(ans,f[j]);
printf("%d\n",ans);
return 0;
}
2.3.4. 多重背包
每個物品i最多可被選\(s_i\)件。
2.3.4.1.單調隊列優化 時間\(O(NM)\) 空間\(O(M)\)
#include<bits/stdc++.h>
using namespace std;
const int N=1005,M=20005;
int n,m;
int v[N],w[N],s[N];
int f[2][M]; //存的是價值
int q[M]; //單調隊列優化，存的是f[(i-1)&1][j]中的j
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d%d%d",&v[i],&w[i],&s[i]);
for(int i=1;i<=n;i++)
for(int r=0;r<v[i];r++){ //r：r=j%v[i]
int hh=0,tt=-1;
for(int j=r;j<=m;j+=v[i]){
while(hh<=tt && j-q[hh]>s[i]*v[i]) hh++;
while(hh<=tt && f[(i-1)&1][q[tt]]+(j-q[tt])/v[i]*w[i]<=f[(i-1)&1][j]) tt--;
q[++tt]=j;
f[i&1][j]=f[(i-1)&1][q[hh]]+(j-q[hh])/v[i]*w[i];
}
}
printf("%d\n",f[n&1][m]);
return 0;
}
2.3.4.2.二進制拆分法 時間\(O(M*(logC_1+logC_2+...+logC_N))\) 空間\(O(M)\)
#include<bits/stdc++.h>
using namespace std;
const int N=12005,M=2005;
int n,m,idx;
int v[N],w[N];
int f[M]; //f[j]：背包中放入總體積為j的物品的最大價值和
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
int a,b,s;
scanf("%d%d%d",&a,&b,&s);
int k=1;
while(k<=s){
idx++;
v[idx]=a*k;
w[idx]=b*k;
s-=k;
k<<=1;
}
if(s>0){
idx++;
v[idx]=a*s;
w[idx]=b*s;
}
}
for(int i=1;i<=idx;i++)
for(int j=m;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+w[i]);
printf("%d\n",f[m]);
return 0;
}
2.3.5. 混合背包
一件物品可以選1、s、\(+\infty\)件。
把多重背包用二進制優化,這樣就變成做多個01背包了。
于是問題就變成01背包和完全背包。
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m;
int v[N],w[N],s[N];
int f[N]; //f[j]：背包中放入總體積為j的物品的最大價值和
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d%d%d",&v[i],&w[i],&s[i]);
for(int i=1;i<=n;i++){
//完全背包
if(!s[i]) for(int j=v[i];j<=m;++j) f[j]=max(f[j],f[j-v[i]]+w[i]);
//把多重背包用二進制優化
//這樣就變成做多個01背包了
else{
//01背包
if(s[i]==-1) s[i]=1;
//二進制優化
for(int k=1;k<=s[i];k*=2){
for(int j=m;j>=k*v[i];j--) f[j]=max(f[j],f[j-k*v[i]]+k*w[i]);
s[i]-=k;
}
/*注意，不可以寫成：
for(int k=0;k<=9;k++) if((s>>k)&1) for(int j=m;j>=v*(1<<k);j--) f[j]=max(f[j],f[j-v*(1<<k)]+w*(1<<k));
因為假設m=7v,s=8，該物品只會被拆成1個體積為8v價值為8w的物品，就什么也放不下，但是本來可以放7個該物品的
*/
if(s[i]) for(int j=m;j>=s[i]*v[i];j--) f[j]=max(f[j],f[j-s[i]*v[i]]+s[i]*w[i]);
}
}
printf("%d\n",f[m]);
return 0;
}
2.3.6. 分組背包 時間\(O(NM)\) 空間\(O(M)\)
給定背包體積，若干個物品的體積、價值和組號，一個組內的物品只能選1件，求最大價值。
由于省略第一維i：前i個組，所以體積要倒序循環。
時間復雜度的計算：對于每一個組i（階段）：\(O(MS_1)+O(MS_2)+\cdots+O(MS_n)=O(M(S_1+S_2+\cdots+S_n))=O(MN)\)。
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m;
int v[N][N],w[N][N],s[N];
int f[N]; //f[j]：背包中放入總體積為j的物品的最大價值和
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&s[i]);
for(int j=1;j<=s[i];j++)
scanf("%d%d",&v[i][j],&w[i][j]);
}
for(int i=1;i<=n;i++) //階段
for(int j=m;j>=0;j--) //狀態
for(int k=1;k<=s[i];k++) //決策
if(v[i][k]<=j) f[j]=max(f[j],f[j-v[i][k]]+w[i][k]);
printf("%d\n",f[m]);
return 0;
}
2.3.7. 有依賴的背包（樹形背包） \(O(NM^2)\)
樹形背包復雜度大。如果：
- “物品體積為1”時，應使用那個樹形dp\(O(N^2)\)，而不是復雜度更高的樹形背包\(O(NM^2)\)。
- 森林中每棵樹的節點都少時，枚舉一棵樹所有的方案分為一組，對森林進行分組背包\(O(NM)\)。
1.f[u][j]：以u為根的子樹從中選出了總體積為j的物品放入背包，物品的最大總價值之和。
1+.如果有森林，建立虛擬源點變為1棵樹。
2.dfs遍歷；
3.先把根節點的體積空出來，
采用分組背包的思想：把每個子樹分組，從每個子樹組中只能選一個子樹的子樹物品組f[][k]（前面已經計算好了f[][k]）。
for(i：循環每個組（子樹）){
int son=e[i];
dfs(son); //dfs遍歷
for(j：循環體積（注意把根節點的體積空出來）)
for(k：循環決策：挑組里的哪個物品（子樹的子樹物品組f[son][k]）)
f[u][j]=max(f[u][j],f[u][j-k]+f[son][k]);
}
4.最后把根節點的體積塞回去。
for(int i=m;i>=1;i--) f[u][i]=f[u][i-1]+w[u];
f[u][0]=0;
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m,root;
int v[N],w[N];
int h[N],e[N],ne[N],idx;
int f[N][N]; //f[u][j]：以u為根的子樹從中選出了總體積為j的物品放入背包，物品的最大總價值之和
void add(int a,int b){
e[++idx]=b;
ne[idx]=h[a];
h[a]=idx;
}
void dp(int u){
for(int i=h[u];i!=0;i=ne[i]){ //循環物品組
int son=e[i];
dp(son);
// 分組背包
for(int j=m-v[u];j>=0;j--) //循環體積,m-v[u]：把根節點的體積空出來
for(int k=0;k<=j;k++) //循環決策,注意這里要取等
f[u][j]=max(f[u][j],f[u][j-k]+f[son][k]);
}
//將物品u加進去
for(int j=m;j>=v[u];j--) f[u][j]=f[u][j-v[u]]+w[u];
for(int j=0;j<v[u];j++) f[u][j]=0;
return ;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
int fa;
scanf("%d%d%d",&v[i],&w[i],&fa);
if(fa==-1) root=i;
else add(fa,i);
}
dp(root);
printf("%d\n",f[root][m]);
return 0;
}
2.3.8. 二維費用背包 時間\(O(NVM)\) 空間\(O(VM)\)
#include<bits/stdc++.h>
using namespace std;
const int N=1005,K=105;
int n,V,M;
int v[N],m[N],w[N];
int f[K][K]; //f[j]：背包中放入總體積為j的物品的最大價值和
int main(){
scanf("%d%d%d",&n,&V,&M);
for(int i=1;i<=n;i++) scanf("%d%d%d",&v[i],&m[i],&w[i]);
for(int i=1;i<=n;i++)
for(int j=V;j>=v[i];j--)
for(int k=M;k>=m[i];k--)
f[j][k]=max(f[j][k],f[j-v[i]][k-m[i]]+w[i]);
printf("%d\n",f[V][M]);
return 0;
}
2.3.9. 背包問題求方案數 時間\(O(NM)\) 空間\(O(M)\)
以01背包問題求方案數為例：
01背包模型\(f[j]\)
正常的模板，不再贅述……
-
最優方案的方案數
路徑追蹤\(g[j]\)
參考于 彩色鉛筆 dalao Orz
狀態表示\(g[j]\)—集合：當前已使用體積恰好是\(j\)的，且價值為最大的方案
狀態表示\(g[j]\)—屬性：方案的數量\(Sum\)
狀態轉移\(g[j]\)：
\(如果f[j]=f[j] 則 g[j]+=g[j]\)
\(如果f[j]=f[j-v[i]]+w[i] 則 g[j]+=g[j-v[i]]\)初始狀態：
g[0][0] = 1小優化
可以把 g 和 f 寫進一個循環里，再判斷 f 的 轉移路徑 的同時用 g 跟蹤 轉移路徑
然后再用 01背包 的 樸素優化，把第一維消掉即可
#include<bits/stdc++.h>
using namespace std;
const int N=1005,MOD=1e9+7;
int n,m,ans;
int w[N],v[N];
int f[N],g[N]; //f[i]：背包中放入總體積為j的物品的最大價值和；g：路徑跟蹤，當前已使用體積恰好是j的，且價值為最大的方案總數
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);
g[0]=1; //這步別忘記！
for(int i=1;i<=n;i++)
for(int j=m;j>=v[i];j--){
int res,tot=0;
//先備份以便比較
res=max(f[j],f[j-v[i]]+w[i]);
//追蹤路徑
if(res==f[j]) tot=(tot+g[j])%MOD;
if(res==f[j-v[i]]+w[i]) tot=(tot+g[j-v[i]])%MOD;
//完畢后賦值
f[j]=res,g[j]=tot;
}
//統計總的滿足條件方案數
for(int j=0;j<=m;j++) if(f[j]==f[m]) ans=(ans+g[j])%MOD;
printf("%d\n",ans);
return 0;
}
-
裝滿背包的方案數
\(f[i]\)：裝滿容量為i的背包的方案數。
邊界：\(f[0]=1\)。
做一遍類01背包。
#include<bits/stdc++.h>
using namespace std;
const int N=2010;
int n,m;
int v[N];
int f[N],g[N];
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&v[i]);
f[0]=1;
for(int i=1;i<=n;i++)
for(int j=m;j>=v[i];j--)
f[j]+=f[j-v[i]];
printf("%d\n",f[m]);
return 0;
}
- 例題：自然數組合
給定 N 個正整數 A1,A2,…,AN，從中選出若干個數，使它們的和為 M，求有多少種選擇方案。
int n,m,a[N],f[M];
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
f[0]=1;
for(int i=1;i<=n;i++)
for(int j=m;j>=a[i];j--)
f[j]+=f[j-a[i]];
printf("%d\n",f[m]);
return 0;
}
#### 拓展1：若去除第i件物品，求裝滿方案數？
方案數具有可減性：
$g[i]$：$f$的備份。
g[0]=1;
for(int i=1;i<=n;i++)
{
for(int j=1;j<=m;j++)
{
if(j<w[i]) g[j]=f[j];
else g[j]=f[j]-g[j-w[i]];//放入第i件物品的過程是f[j]+=g[j-w[i]]，其中g去除了第i件物品，于是現在放入1個第i件物品。故逆過程是g[j]=f[j]-g[j-w[i]]
}
printf("%d\n",g[m]);
}
#### 拓展2：完全背包裝滿背包的方案數
$f[i]$：裝滿容量為i的背包的方案數。
邊界：f[0]=1。
做一遍類完全背包。
f[0]=1;
for(int i=1;i<=n;i++)
for(int j=v[i];j<=m;j++)
f[j]+=f[j-v[i]];
printf("%d\n",f[m]);
- 例題1：自然數拆分
給定一個自然數 N，要求把 N 拆分成若干個（≥2）正整數相加的形式。參與加法運算的數可以重復，拆分方案不考慮順序，求拆分的方案數 mod2147483648 的結果。
f[0]=1;
for(int i=1;i<=n;i++)
for(int j=i;j<=n;j++)
f[j]=(f[j]+f[j-i])%MOD;
printf("%lld\n",((f[n]-1)%MOD+MOD)%MOD);//f[n]-1：拆分成>=2個正整數
- [例題2：NOIP2018提高組貨幣系統](https://www.acwing.com/problem/content/534/)
手動模擬觀察性質：
1. $a_1,\dots,a_n $的數都能被$ b_1,\dots,b_m$ 表示出來。（顯然成立）
2. 在最優解中， $b_1,\dots,b_m$ 一定都是從 $a$中選出來的。
3. $b_1,\dots,b_m $一定不能被其它 $b_i$ 表示出來。（顯然成立）
綜合以上性質，我們得到了如下算法流程：
1. 將 a從小到大排個序。
2. 對于 a 中的每一項 $a_i$ ，判斷其能否被$a_1\sim a_{i-1}$間的數表示（完全背包裝滿背包的方案數，f[a[i]]的方案數≥1就能被表示）。若能，則 $a_i$ 不必選，否則要選 $a_i$ 。
#include<bits/stdc++.h>
using namespace std;
const int N=110,M=3e4;
int t,n,ans;
int a[N];
int f[M];
int main()
{
scanf("%d",&t);
while(t--)
{
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
sort(a+1,a+n+1);
ans=0;
memset(f,0,sizeof f);
f[0]=1;
for(int i=1;i<=n;i++)
{
if(f[a[i]]==0) ans++;
for(int j=a[i];j<=a[n];j++) f[j]+=f[j-a[i]];
}
printf("%d\n",ans);
}
return 0;
}
2.3.10. 背包問題求具體方案
以01背包問題求具體方案為例：
01背包模型\(f[i][j]\)
注意：由于本題路徑追蹤需要輸出具體方案，故必須開二維狀態\(f[i][j]\)。
\(path[i]\)：單純記一下路徑答案，而非狀態轉移
-
遞推寫法
轉載自 彩色鉛筆 dalao Orz
輸出方案 其實就是輸出方案的 轉移路徑。
先做一遍正常的 背包DP ，然后從 目標狀態 倒推回 初始狀態 的整個 轉移路徑 即可；
說的白話一點就是，在考慮第 i 件物品時，選擇了 選 還是 不選 的策略到達了第 i+1 件物品。
int v = V; // 記錄當前的存儲空間
// 因為最后一件物品存儲的是最終狀態，所以從最后一件物品進行循環
for (從最后一件循環至第一件)
{
if (g[i][v])
{
選了第 i 項物品;
v -= 第 i 項物品的價值;
} else
未選第 i 項物品;
}
題目里還要求了輸出 **字典序最小的方案**；
而在倒推 狀態轉移路徑 的時候，只能在 分叉轉移 的時候，即 當前 物品既可以 選 又可以 不選 時，優先 選；
因此，我們本題的 背包DP 需要倒過來（從N遞推到1）做，然后再 從1倒推回N 找出路徑；
這樣在抉擇時，如果出現 分叉轉移，我們就優先 選 當前物品即可。
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m;
int v[N],w[N];
int f[N][N]; //f[i][j]：從前i種物品選出總體積為j的物品放入背包，物品的最大價值和
int path[N],pidx; //記錄答案
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);
//01背包dp樸素做法
for(int i=n;i>=1;i--) //為了輸出字典序最小的方案
for(int j=0;j<=m;j++){ //01背包的樸素做法j是正序循環
f[i][j]=f[i+1][j];
//選了i
if(j>=v[i]) f[i][j]=max(f[i][j],f[i+1][j-v[i]]+w[i]); //i+1：因為i倒序循環
}
//從目標狀態倒推回初始狀態的整個轉移路徑
for(int i=1,j=m;i<=n;i++)
if(j>=v[i] && f[i][j]==f[i+1][j-v[i]]+w[i]){ //選了i
path[++pidx]=i;
j-=v[i];
}
for(int i=1;i<=pidx;i++) printf("%d ",path[i]);
puts("");
return 0;
}
-
遞歸寫法
當然也可以從 拓撲圖 的角度來 分析理解，具體可以參考 彩色鉛筆dalao的博客：【分組背包+背包DP輸出方案—拓撲圖分析】 ，里面也有 遞歸\(**DFS**\)迭代 的寫法(其實就是在跟蹤狀態轉移的路徑）
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m;
int v[N],w[N];
int f[N][N]; //f[i][j]：從前i種物品選出總體積為j的物品放入背包，物品的最大價值和
int path[N],pidx; //路徑追蹤
//從終點倒推回起點的整個拓撲圖路徑
void dfs(int i,int j,int last){
if(i==0) return ;
for(int a=last+1;a<=n;a++)
if(j>=v[a] && f[a][j]==f[a+1][j-v[a]]+w[a]){ //選了a
path[++pidx]=a;
dfs(n-1,j-v[a],a);
return ;
}
return ;
}
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);
//01背包dp樸素做法
for(int i=n;i>=1;i--) //為了輸出字典序最小的方案
for(int j=0;j<=m;j++){ //01背包的樸素做法j是正序循環
f[i][j]=f[i+1][j];
//選了i
if(j>=v[i]) f[i][j]=max(f[i][j],f[i+1][j-v[i]]+w[i]); //i+1：因為i倒序循環
}
//從目標狀態倒推回初始狀態的整個轉移路徑
dfs(n,m,0);
for(int i=1;i<=pidx;i++) printf("%d ",path[i]);
puts("");
return 0;
}
2.3.11附錄
輔助感性理解
01背包樸素做法
樸素線性dp \(O(NM)\)
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m;
int v[N],w[N];
int f[N][N]; //f[i][j]：從前i種物品選出總體積為j的物品放入背包，物品的最大價值和
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++){
f[i][j]=f[i-1][j];
//放得下
if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
}
printf("%d\n",f[n][m]);
return 0;
}
滾動數組優化 時間\(O(NM)\) 空間\(O(M)\)
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m;
int v[N],w[N];
int f[2][N]; //f[i][j]：從前i種物品選出總體積為j的物品放入背包，物品的最大價值和
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++){
f[i&1][j]=f[(i-1)&1][j];
//放得下
if(j>=v[i]) f[i&1][j]=max(f[i&1][j],f[(i-1)&1][j-v[i]]+w[i]);
}
printf("%d\n",f[n&1][m]);
return 0;
}
完全背包樸素做法 \(O(NM)\)
#include<bits/stdc++.h>
using namespace std;
const int N=1005;
int n,m;
int v[N],w[N];
int f[N][N]; //f[i][j]：從前i種物品選出總體積為j的物品放入背包，物品的最大價值和
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++){
f[i][j]=f[i-1][j];
//放得下
if(j>=v[i]) f[i][j]=max(f[i][j],f[i][j-v[i]]+w[i]); //注意這里和01背包不同：由狀態i轉移過來
}
printf("%d\n",f[n][m]);
return 0;
}
多重背包樸素做法：直接拆分法 時間\(O(M*(C1+C2+...+CN))\) 空間\(O(M)\)
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m,ans;
int v[N],w[N],s[N];
int f[N]; //f[j]：背包中放入總體積為j的物品的最大價值和
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d%d%d",&v[i],&w[i],&s[i]);
for(int i=1;i<=n;i++)
for(int k=1;k<=s[i];k++)
for(int j=m;j>=v[i];j--)
f[j]=max(f[j],f[j-v[i]]+w[i]);
printf("%d\n",f[m]);
return 0;
}
分組背包樸素做法 時間\(O(NM)\) 空間\(O(MS)\)
#include<bits/stdc++.h>
using namespace std;
const int N=105;
int n,m;
int v[N][N],w[N][N],s[N];
int f[N][N]; //f[i][j]：只從前i組物品中選，當前體積小于等于j的最大價值和
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++){
scanf("%d",&s[i]);
for(int j=1;j<=s[i];j++)
scanf("%d%d",&v[i][j],&w[i][j]);
}
for(int i=1;i<=n;i++) //階段
for(int j=m;j>=0;j--){ //狀態
f[i][j]=f[i-1][j];
//選
for(int k=1;k<=s[i];k++) //決策
if(v[i][k]<=j)
f[i][j]=max(f[i][j],f[i-1][j-v[i][k]]+w[i][k]);
}
printf("%d\n",f[n][m]);
return 0;
}
背包問題求方案數樸素做法 時間\(O(NM)\) 空間\(O(NM)\)
#include<bits/stdc++.h>
using namespace std;
const int N=1005,MOD=1e9+7;
int n,m,ans;
int w[N],v[N];
int f[N][N],g[N][N]; //f[i][j]：從前i種物品選出總體積為j的物品放入背包，物品的最大價值和；g：路徑跟蹤，從前i種物品中當前已使用體積恰好是j的，且價值為最大的方案總數
int main(){
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++) scanf("%d%d",&v[i],&w[i]);
//樸素01背包dp
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++){
f[i][j]=f[i-1][j];
//選
if(j>=v[i]) f[i][j]=max(f[i][j],f[i-1][j-v[i]]+w[i]);
}
//追蹤路徑
g[0][0]=1; //這步別忘記！
for(int i=1;i<=n;i++)
for(int j=0;j<=m;j++){
//可以由不選轉移過來
if(f[i][j]==f[i-1][j]) g[i][j]=(g[i][j]+g[i-1][j])%MOD;
//這里不可以直接用else
//可以由選轉移過來
if(j>=v[i] && f[i][j]==f[i-1][j-v[i]]+w[i]) g[i][j]=(g[i][j]+g[i-1][j-v[i]])%MOD;
}
//統計總的滿足條件方案數
for(int j=0;j<=m;j++) if(f[n][j]==f[n][m]) ans=(ans+g[n][j])%MOD;
printf("%d\n",ans);
return 0;
}
2.3.12.應用
將題意抽象為背包問題：→背包容積、→物品、→物品的體積、→物品的價值、→每種物品選幾個、→求Max/Min/方案數\(\Rightarrow\)xx背包模型。
2.4.狀態機模型
特征：不同狀態之間有可以互相轉移的過程，\(e.g.\)股票可以從買轉移到賣，然后又從賣轉移到買。而背包模型物品放入背包后就不會再拿出來了，沒有可以互相轉移的過程。
狀態機強調過程，考慮從上一個時間點的各個狀態轉移到現在的狀態。
\(f[當前階段,狀態]\)
邊界：\(\begin{cases} 若合法：f[0,bool]=0 \\ 若不合法：f[0,bool]=-INF \end{cases}\)
1.4.1.股票買賣I
每天股票有不同的價格，不能同時參與多筆交易（即必須在再次購買前出售掉之前的股票），可以多次交易，求最大利益。
狀態機模型如下：
\(f[i][bool]\)：前i天且第i天是否持有股票狀態的最大利益
狀態轉移：\(\begin{cases} f[i][0]=\max(f[i-1][0],f[i-1][1]+w[i]) \\ f[i][1]=\max(f[i-1][0]-w[i],f[i-1][1]) \end{cases}\)
邊界：\(f[0][0]=0\),\(f[0][1]=-INF\)
答案：顯然第n天一定是賣出股票才能得到最大利益：\(f[n][0]\)
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&w[i]);
f[0][0]=0,f[0][1]=-INF;
for(int i=1;i<=n;i++)
{
f[i][0]=max(f[i-1][0],f[i-1][1]+w[i]);
f[i][1]=max(f[i-1][0]-w[i],f[i-1][1]);
}
printf("%d\n",f[n][0]);//第n天一定是賣出股票才能得到最大利益
1.4.2.股票買賣II
每天股票有不同的價格，不能同時參與多筆交易（即必須在再次購買前出售掉之前的股票），最多k次交易，每筆交易都有f的手續費，求最大利益。
“最多k次交易”：再開一維\(f[i,j,bool]\)：前i天，完成的完整交易數是j，且第i天是否持有股票狀態的最大利益。
“每筆交易都有f的手續費”：直接把f加入方程，當狀態0→1或1→0增加手續費。
1.4.3.股票買賣III
每天股票有不同的價格，不能同時參與多筆交易（即必須在再次購買前出售掉之前的股票），賣出股票后進入1天冷凍期無法在第二天買入股票，可以多次交易，求最大利益。
多了一個“冷凍期”狀態不要緊，用狀態機在前一天3個狀態進行轉移。
\(f[i][bool]\)：前i天且第i天是否持有股票狀態的最大利益
狀態轉移：\(\begin{cases} f[i][0]=\max(f[i-1][0],f[i-1][2]) \\ f[i][1]=\max(f[i-1][0]-w[i],f[i-1][1]) \\ f[i][2]=f[i-1][1]+w[i] \end{cases}\)
邊界：\(f[0][0]=0\),\(f[0][1]=f[0][2]=-INF\)
答案：顯然第n天一定是賣出股票才能得到最大利益：\(\max(f[n][0],f[n][2])\)
2.5.區間dp\(O(N^3)\)
適用條件：連續+合并。
- 每次操作是合并相鄰的元素。\(e.g.\)區間石子合并。
- 染色問題。\(e.g.\)Paint。
- 每次操作是彈出一個序列的頭或尾。\(e.g.\)矩陣取數游戲。
- 每次操作是對連續的一段操作。\(e.g.\)字符串折疊。
- 狀態是連續的一段。\(e.g.\)關路燈。
階段：區間長度。狀態：區間的左、右端點。決策：劃分區間的方法，分界點。
轉移：由2個（或若干個）組成它的區間（顯然比它更小（已算出dp值）且包含于它）所代表的狀態轉移而來。難點在于枚舉分界點。
邊界：長度為1的“元區間”。
同時為了快速計算區間，一般預處理前綴和。
答案：
- 如果問的是將多個元素合并為一個元素，最終那一個元素的最值：輸出f[1][n]。
- 如果問的是合并中出現的最值：用\(max\)把轉移過程中的所有最大值全部記錄下來。輸出\(max\)。
2.5.1.區間dp——區間石子合并
\(f[l][r]\)：把區間第l堆和第r堆石子合并成一堆需要消耗的最小體力。
狀態轉移：\(f[l][r]=\min\limits_{l≤k<r} \{ f[l][k]+f[k+1][r] \} + \sum\limits_{i=l}^{r} a[i]\)。
邊界：\(\forall l \in [1,N],f[l][l]=0\)，其余為正無窮。
目標：\(f[1][N]\)。
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&m[i]);
f[i][i]=0;//長度為1的“元區間”
sum[i]=sum[i-1]+m[i];//預處理前綴和
}
memset(f,0x3f,sizeof f);
for(int len=2;len<=n;len++/*階段*/)
for(int l=1;l+len-1<=n;l++/*狀態：左端點*/){
int r=l+len-1;//狀態：右端點
for(int k=l;k<r;k++/*決策。注意是左閉右開，因為兩個區間是l~k、k+1~r*/) f[l][r]=min(f[l][r],f[l][k]+f[k+1][r]);
f[l][r]+=sum[r]-sum[l-1];
}
printf("%d\n",f[1][n]);
2.5.2.區間dp求具體方案
追蹤數組\(g[l][r]\)：存儲使f[l][r]=calc(f[l][k],f[k+1][r])有最值的k。
輸出方案：
void dfs(int l,int r)
{
if(l>r) return ;
printf("%d ",g[l][r]);
dfs(l,g[l][r]);
dfs(g[l][r]+1,r);
return ;
}
for(int l=1;l<=n;l++) g[l][l]=0;
dfs(1,n);
2.5.3.區間dp——染色問題
設計狀態：
- 要求染成給定的顏色：\(f[l][r]\)：把[l,r]染成給定的顏色的最小代價。
- 要求染成同一種顏色：\(f[l][r]\)：把[l,r]染成同一種顏色a[r]的最小代價。
狀態轉移方程：\(f[l][r]=\min\{f[l][k]+f[k+1][r]+[真值表達式]\}\)。
優化：可以把真值表達式拆成2個方程：\(f[l][r]=\min\{f[l+1][r],f[l][r-1]\}+?,f[l][r]=\min\{f[l][k]+f[k+1][r]\}+?\)。
2.5.3.區間dp與樹的序列
樹形結構的dp可以通過樹的序列（下面以二叉樹的中序遍歷為例）用區間dp解決。
\(f[l][r]\)：所有中序遍歷是[l,r]這一段的二叉樹的集合。
劃分區間時：k：當前子樹的根；[l,k-1]：左子樹；[k+1,r]：右子樹。
于是循環決策k時，閉區間：for(int k=l;k<=r;k++)。
當kl時，左子樹為空；當kr時，右子樹為空。
目標：整顆樹f[l][r]。
2.5.4.二維區間dp
平面dp。
\(f[x_1][y_1][x_2][y_2]\)：子矩陣(x1,y1)(x2,y2)……
劃分方法：分成兩個子矩陣：(x1,y1)(i,y2)+(i+1,y1)(x2,y2)或(x1,y1)(i,y2)+(i+1,y1)(x2,y2)或(x1,y1)(x2,i)+(x1,i+1)(x2,y2)或(x1,y1)(x2,i)+(x1,i+1)(x2,y2)。
預處理二維前綴和。
由于循環層數太多，采用記憶化搜索。
- 例題：NOI1999棋盤分割
#include<bits/stdc++.h>
using namespace std;
const int N=15,M=9;
const double INF=1e9;
int n;
int s[M][M];
double f[M][M][M][M][N];
double X;
int get_sum(int x1,int y1,int x2,int y2)
{
return s[x2][y2]-s[x1-1][y2]-s[x2][y1-1]+s[x1-1][y1-1];
}
double get(int x1,int y1,int x2,int y2)
{
double sum=get_sum(x1,y1,x2,y2)-X;
return 1.0*sum*sum/n;
}
double dp(int x1,int y1,int x2,int y2,int k)
{
double &v=f[x1][y1][x2][y2][k];
if(v>=0) return v;
if(k==1) return v=get(x1,y1,x2,y2);
v=INF;
for(int i=x1;i<x2;i++)
{
v=min(v,get(x1,y1,i,y2)+dp(i+1,y1,x2,y2,k-1));
v=min(v,dp(x1,y1,i,y2,k-1)+get(i+1,y1,x2,y2));
}
for(int i=y1;i<y2;i++)
{
v=min(v,get(x1,y1,x2,i)+dp(x1,i+1,x2,y2,k-1));
v=min(v,dp(x1,y1,x2,i,k-1)+get(x1,i+1,x2,y2));
}
return v;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=8;i++)
for(int j=1;j<=8;j++)
{
scanf("%d",&s[i][j]);
s[i][j]+=s[i-1][j]+s[i][j-1]-s[i-1][j-1];
}
X=1.0*s[8][8]/n;
memset(f,-1,sizeof f);
printf("%.3lf\n",sqrt(dp(1,1,8,8,n)));
return 0;
}
2.6.類Floyd模型\(O(N^3)\)
適用條件：求2點間滿足特殊要求/特殊計算代價方式的最短路。
\(f_{k,i,j}\)：經過若干個編號不超過k的節點（不包括起終點），從i到j的最短路長度。
狀態轉移：\(f_{k,i,j}=min(f_{k-1,i,j},f_{k-1,i,k}\oplus f_{k-1,k,j})\)。
邊界：\(f_{0,i,j}=d_{i,j}\)。其中d為鄰接矩陣。
第一維可以省略。
2.6.1.計算代價的方式是路徑上編號的最值\(O(N^3+\log N)\)
原最值問題較難求解，應轉化為二分+可行問題。
\(f_{k,i,j}\)：布爾數組，經過若干個編號不超過k的節點（不包括起終點），從i到j是否可達。
狀態轉移：\(f_{k,i,j}=f_{k-1,i,j}|(f_{k-1,i,k}\&f_{k-1,k,j})\)。
使用bitset優化：
bitset<N> f[N][N];
for(int i=1;i<=n;i++) for(int j=1;j<=n;j++) if(d[i][j]) f[0][i][j]=1;//邊界
for(int k=1;k<=n;k++)
for(int i=1;i<=n;i++)
{
f[k][i]=f[k-1][i];
if(f[k-1][i][k]) f[k][i]|=f[k-1][k];
}
邊界：\(f_{0,i,j}=d_{i,j}\)。其中d為鄰接矩陣。
k從小到大二分找到第一個\(f_{k,s,t}\)為true的k，即為答案。
注意dp數組不包括起終點的信息，因此最終答案要根據題意判斷是否對起終點的編號取最值。
2.6.2.類Floyd與廣義矩陣乘法
2.7.序列·插入·連續段模型\(O(N^2)\)
適用條件：序列問題。當且僅當i,j相對大小關系確定時，(i,j)的貢獻可拆開i,j獨立計算；或轉移要求滿足相鄰左右相對大小關系。
將原題意轉化為將n個元素\(a_i\)從小到大依次插入n個空位，當前相鄰的元素形成1個連續段。插入實際上是插空法，“空”：空隙，而不是具體第幾個空位。連續段之間欽定有序。
從小到大插入的意義：插入的元素>之前已經插入的元素，插入的元素<還沒有插入的元素。這樣當插入元素時，就已經知道了它與左右相鄰元素的相對大小關系，可以獨立確定i的貢獻。
下面以dp求方案數為例：
\(f_{i,j,d}\)：從小到大插入了i個元素，形成了j個連續段，確定了d（\(d\in[0,2]\)）個起/終點（空位的最左/右邊）。
轉移：
要注意特殊處理起/終點。
-
\(a_i\)插入到某個連續段的兩邊之一。
-
\(a_i\)不作為起/終點。
\(f_{i,j,d}←f_{i-1,j,d}*(2*j-d)\)。(2j-d)：除了起/終點的左/右邊不能插入，\(a_i\)可選擇每個連續段的左/右邊中的一個插入。
-
\(a_i\)作為起/終點。
\(f_{i,j,d}←f_{i-1,j,d-1}*(2-(d-1))\)。
-
-
\(a_i\)插空當前單獨作為新的連續段。
-
\(a_i\)不作為起/終點。
\(f_{i,j,d}←f_{i-1,j-1,d}*(j-d)\)。*(j-d)：除了起/終點的左/右邊不能插空，原來j-1個連續段有j個空供\(a_i\)插空。
-
\(a_i\)作為起/終點。
\(f_{i,j,d}←f_{i-1,j-1,d-1}*(2-(d-1))\)。
-
-
\(a_i\)插入到兩個連續段之間，合并兩個連續段成為一個大連續段。
\(f_{i,j,d}←f_{i-1,j+1,d}*j\)。*j：原來j+1個連續段之間有j個空供\(a_i\)合并。
邊界：\(f_{0,0,0}=1\)。
\(ANS=f_{n,1,2}\)。
注意要特判n=1時的情況，因為當n=1時1個點同時作為起/終點。
2.8.拍賣會模型
3.樹形dp
-
給定一棵無根樹，我們可以任選一個節點為根。
-
一般以節點從深到淺（子樹從小到大）的順序作為dp的“階段”。狀態表示中第一維通常是節點編號（以u為根節點的子樹）。
\(f[u]\)：以u為根節點的子樹。
-
對于每個點，假設其是葉子節點，為其設定正確的邊界條件（初值），然后一般可以自然處理不合法情況。
-
狀態轉移：考慮一條樹邊(u,v)。
-
樹形dp和線性dp在轉移上有本質上的不同。
樹形dp
-
//先決定點u上的物品
siz[u]=1;
f[u][0]=//不選擇點u上的物品
f[u][1]=//選擇點u上的物品
f[u][j+k/*注意這里不需要考慮點u是否選擇，因為在上面已經考慮過了*/]=max(f[u][j+k],f[u][j]+f[v][k]);
線性dp
f[u][k]=max(f[u][k],f[v][k]);//不選擇點u上的物品
f[u][k+1]=max(f[u][k+1],f[v][k]);//選擇點u上的物品
在回溯時，從子結點向節點x進行狀態轉移。
- 當點u在其的當前層時，f[u]表示點u與已合并的子樹的信息。故f[u]的邊界（初始值）表示單獨一個點u的信息。
- 當點u即將回溯時，由于所有的子樹信息都已經合并到點u，故此時f[u]才真正表示設計狀態時的定義：以u為根的子樹……
技巧
- 子樹與子樹間計算貢獻，使用一次把子樹加入點u，每次把新加的子樹和已經加入的子樹（信息在點u上）計算貢獻\(O(N)\)。而不是枚舉子樹與子樹\(O(N^2)\)。
- 計算方案數時，對于同一個v：加法原理；不同的v：乘法原理。
- f[v]不會考慮點u的狀態。
- 有些樹形結構的dp可以通過樹的序列用區間dp解決，參見《動態規劃2.5.3.區間dp與樹的序列》。
3.1.樹形dp——求樹的直徑
DP的實質就是從集合的角度把每個方案歸類，統一考慮。這里我們采取按點分類的方法。具體來說，我們任選一個點作為根節點，使這棵樹成為一棵有根樹。對于每個點 u ，點 u 及其子樹的直徑有兩種情況：1.直徑沒有經過點 u；2.直徑經過點 u 。
對于第 1 種情況，我們直接枚舉 u 的每棵子樹的直徑再求個 max ；對于第 2 種情況，我們求出子樹中所有節點到 u 的路徑，取最大的兩個相加即可。最后兩種情況得到的答案再取一個 max就是 u 子樹直徑的最終答案。
int d[N]; //d[i]：從i出發以i為根的子樹，能到達最遠的距離
void dp(int u,int fa)
{
for(int i=h[u];i!=0;i=ne[i])
{
int j=e[i];
if(j==fa) continue;
dp(j,u);
//注意下面的代碼兩行順序不能反?。?！
length=max(length,d[u]+d[j]+w[i]);
d[u]=max(d[u],d[j]+w[i]);
}
return ;
}
3.2.樹形dp與合并子樹信息模型（size和m剪枝）\(\min \{O(N^2),O(NM)\}\)
適用條件：1.\(f[u][i]\)：以u為根的子樹且選了i個物品的最值。2.常見樹形dp，樹形計數dp；3.信息可被拆分到子樹。
若有依賴關系——結合狀態機模型：\(f[u][i][bool]\)：以u為根的子樹、選了i個物品且點u上的物品有沒有選的最值。
-
當點u在其的當前層時，f[u]表示點u與已合并的子樹的信息。故f[u]的邊界（初始值）表示單獨一個點u的信息。
邊界：先決定點u上的物品。f[u][0]=不選擇點u上的物品，f[u][1]=選擇點u上的物品。
-
當點u即將回溯時，由于所有的子樹信息都已經合并到點u，故此時f[u]才真正表示設計狀態時的定義：以u為根的子樹……
子樹依次向其父親節點合并信息。
使用siz[u]（以u為根的子樹大?。┘糁σ员ＷC復雜度。
時間復雜度
\(O(N^2)\)：siz[u]在加入子樹v前先進行轉移，相當于是統計點對(a,b)，而點對(a,b)一共有\(O(N^2)\)個，且只在lca(a,b)被統計一次。因此復雜度是\(O(N^2)\)。
-
\(O(NM)\)
![]()
不能高效換根。
int siz[N];//siz[u]：以u為根的子樹大小
int f[N][N]; //f[u][i]以u為根的子樹且選了i個物品的最大價值
int backup[N];//備份數組
void dfs(int u,int fa)
{
//先決定點u上的物品
siz[u]=1;
f[u][0]=//不選擇點u上的物品
f[u][1]=//選擇點u上的物品
for(int i=h[u];i!=0;i=ne[i])
{
int v=e[i];
if(v==fa) continue;
dfs(v,u);
//備份數組是因為f[u][j+k]的信息會更新
//注意更新到下標為siz[u]為止，否則復雜度將不能保證
for(int j=0;j<=siz[u];j++)
{
backup[j]=f[u][j];
f[u][j]=0;//計數類問題賦成0，最值問題賦成無窮大/小
}
//m是題目問題中“樹上選擇m個物品的最大價值”中的m
for(int j=0;j<=min(m,siz[u])/*此處的siz[u]是加入子樹v前的大小，兩個元素取min缺一不可*/;j++)
for(int k=0;k<=min(m-j,siz[v]);k++)
f[u][j+k]=max(f[u][j+k],backup[u][j]/*注意這里使用backup*/+f[v][k]);
siz[u]+=siz[v];//注意這里才加上siz[v]?。?！
}
return ;
}
//恰好選m個
printf("%d\n",f[root][m]);
//最多選m個
int ans=-INF;
for(int i=0;i<=m;i++) ans=max(ans,f[root][i]);
printf("%d\n",ans);
3.3.樹形dp與背包模型\(O(NM^2)\)
采見《動態規劃2.3.7. 有依賴的背包（樹形背包） 》
注意
- 當森林中每棵樹的節點都少時，枚舉一棵樹所有的方案分為一組，對森林進行分組背包\(O(NM)\)。
- 樹形背包采用樹上選物品模型，只能減小常數，不能減小時間復雜度為\(\min \{O(N^2),O(NM)\}\)。因為一個物品有了體積的維度，根據樹上選物品模型的時間復雜度分析，此時時間復雜度最壞仍為\(O(NM^2)\)。
3.4.樹形dp與狀態機模型
特征：子結點的狀態會影響父節點的狀態。
\(f[u][bool]\)：以u為根的子樹，且節點u處于bool狀態……
遞歸回溯時，將當前節點不同的狀態由對應的子結點的狀態轉移過來。
3.4.1.父子相互制約模型
特征：父節點的狀態和子節點的狀態相互制約影響。
下面以“定義選擇一個點，與這個點直接相連的點都會被染色。在樹上選擇最少的點，使得所有點都被染色。”為例。
當前節點u有3個狀態：f[u][0]：當前節點的父節點被選擇，當前節點不用被選擇；f[u][1]：當前節點的其中一個子結點被選擇，當前節點不用被選擇。f[u][2]：當前節點被選擇；
賦上邊界條件（初值）：\(f_{i,2}=1\)。
其中值得注意的2個地方是：1. 狀態0雖然信息與父節點有關，但是仍然是由子結點轉移過來。2. f[v]不會考慮點u的狀態。
\(f_{i,0}=\sum\limits_{j\in son_i}\min(f_{j,1},f_{j,2})\)
\(f_{i,1}=\min\limits_{k\in son_i}(f_{k,2}+\sum_{j\in son_i-\{k\}}\min(f_{j,1},f_{j,2}))\)
\(f_{i,2}=\sum\limits_{j\in son_i}\min(f_{j,0},f_{j,1},f_{j,2})\)
3.4.2.不相交鏈模型
適用條件：從樹上選出若干條不相交的鏈。
\(f[u][i][0\sim 2]\)：以u為根的子樹中，選了i條鏈，且
-
0：點u還沒開始接鏈。不計入鏈的數量。
當在點u的階段時，該狀態為未選點u。
當點u作為其他點的兒子時，該狀態不用于轉移。（因為此時其含義與狀態2：點u不會再與其他點接了是有重疊的，在回溯時把這種情況歸為狀態2）
-
1：點u正在接鏈。不計入鏈的數量。
當在點u的階段時，該狀態為1條正在接的直鏈。不包含單獨一點u成鏈（因為點u在2=1+1的轉移時會導致單獨一點u成鏈+點v正在接的鏈誤轉移到點u接1條拐彎的鏈，但是單獨一點u成鏈+點v正在接的鏈=點u正在接1條直鏈）。
當點u作為其他點的兒子時，該狀態額外包含：單獨一點u成鏈。
-
2：點u接完了已閉合的鏈，不會再與其他點接了。計入鏈的數量。
當在點u的階段時，該狀態為1條拐彎的鏈。
當點u作為其他點的兒子時，該狀態額外包含：不選點u、1條已閉合的直鏈。
邊界：f[u][0][0]=初值。其他都賦為不合法。
狀態轉移：
“選了i條鏈”：配合樹上選物品模型做到\(\min \{O(N^2),O(NM)\}\)。
-
當在點u的階段時，對于一條邊\((u,v)\)：注意使用備份數組！
\(f[u][j+k][0]←f[u][j][0]+f[v][k][2]\)
\(f[u][j+k][1]←f[u][j][1]+f[v][k][2]\)
\(f[u][j+k][1]←f[u][j][0]+f[v][k][1]\)
\(f[u][j+k][2]←f[u][j][2]+f[v][k][2]\)
\(f[u][j+k+1][2]←f[u][j][1]+f[v][k][1]\)
-
當回溯時，即點u將作為其他點的兒子時，f[u]將額外包含一些狀態：注意下面的順序！
\(f[u][i][1]←f[u][i][0]\)，單獨一點u成鏈。
\(f[u][i][2]←f[u][i][0]\)，不選點u。
\(f[u][i+1][2]←f[u][i][1]\)，注意此時的f[u][i][1]是在\(f[u][i][1]←f[u][i][0]\)更新之后的f[u][i][1]。
答案：\(ans=f[root][i][2]\)。
- 例題：求在n個點的樹上選擇k條不相交的鏈的方案數。
void dfs(int u,int fa)
{
siz[u]=1;
f[u][0][0]=1;
for(int i=h[u];i!=0;i=ne[i])
{
int v=e[i];
if(v==fa) continue;
dfs(v,u);
for(int j=0;j<=siz[u];j++)
{
memcpy(backup[j],f[u][j],sizeof f[u][j]);
memset(f[u][j],0,sizeof f[u][j]);
}
for(int j=0;j<=siz[u];j++)
for(int k=0;k<=siz[v];k++)
{
add(f[u][j+k][0],backup[j][0]*f[v][k][2]%MOD);
add(f[u][j+k][1],backup[j][1]*f[v][k][2]%MOD);
add(f[u][j+k][1],backup[j][0]*f[v][k][1]%MOD);
add(f[u][j+k][2],backup[j][2]*f[v][k][2]%MOD);
if(j+k+1<=siz[u]+siz[v]) add(f[u][j+k+1][2],backup[j][1]*f[v][k][1]%MOD);
}
siz[u]+=siz[v];
}
for(int i=0;i<=siz[u];i++)
{
add(f[u][i][1],f[u][i][0]); //當點u作為其他點的兒子時，點u正在接鏈包含單獨一點u成鏈
add(f[u][i][2],f[u][i][0]); //當點u作為其他點的兒子時，點u接完了已閉合的鏈（不會再與其他點接了）包含點u還沒開始接鏈（不選點u）
if(i+1<=siz[u]) add(f[u][i+1][2],f[u][i][1]); //當點u作為其他點的兒子時，點u接完了已閉合的鏈（不會再與其他點接了）包含點u接了1條已閉合的直鏈
}
return ;
}
printf("%lld\n",f[n][k][2]);
3.5.換根dp（二次掃描與換根法）
特征：給定一棵無根樹，需要計算以每個節點為根的整棵樹的信息。
- 先考慮直接選點1為根，如何做具有可逆性的（不可逆性的則需要額外的技巧，見下文。）dp（\(f[u]\)：以u為根的子樹……。若點u是整棵樹根節點，則以u為根的子樹即為以u為根的整棵樹。）使得能求出點1的答案。
- 下面分為三種類型。一道題目可能會同時用到多種類型。
-
類型一
init(u)：初始化：假設點u是葉子節點，為其設定正確的邊界條件（初值）。merge(u,v)：正常樹形dp的轉移：從以兒子v為根的子樹到以u為根的子樹的狀態轉移。split(u,v)：merge(u,v)的逆操作：從已執行“從以兒子v為根的子樹到以u為根的子樹的狀態轉移”，還原到未執行其。若`merge(u,v)`的操作序列為$\{A_1,\cdots,A_x\}$，則`split(u,v)`的操作序列為$\{A_x^{-1},\cdots,A_1^{-1}\}$。 #### 不可逆操作的處理 將f[v]排成一行，通過補集（前后綴）的信息求得不含f[v]的f[u]。
-
vector<int> e[N];//使用基于vector的鄰接表，以便前后綴處理
void dfs2(int u,int fa)
{
/*若e[u]不含fa，則需要特判：if(e[u].empty()) return ;*/
vector<type> p(e[u].size()),s(e[u].size());//前后綴
p[0]=f[e[u][0]];
for(int i=1;i<e[u].size();i++) /*把p[i-1]和f[e[u][i]]合并到p[i]*/
s[e[u].size()-1]=f[e[u].back()];
for(int i=e[u].size()-2;i>=0;i--) /*把s[i+1]和f[e[u][i]]合并到s[i]*/
for(int i=0;i<e[u].size();i++)
{
int v=e[u][i];
if(v==fa) continue;
init(u);
if(i-1>=0) /*把p[i-1]合并進f[u]*/
if(i+1<e[u].size()) /*把s[i+1]合并進f[u]*/
/*已得到不含f[v]的f[u]，進行后續操作……*/
dfs2(v,u);
/*……*/
}
/*還原f[u]：
方法一：通過p和s求得不含f[fa]的f[u]。
方法二：使用備份。
*/
return ;
}
split(u,v);
merge(v,u);
`calc(u)`：計算以u為根的整棵樹的信息。
void dfs1(int u,int fa)
{
init(u);
for(int i=h[u];i;i=ne[i])
{
int v=e[i];
if(v==fa) continue;
dfs1(v,u);
merge(u,v);
}
return ;
}
void dfs2(int u,int fa)
{
calc(u);
for(int i=h[u];i;i=ne[i])
{
int v=e[i];
if(v==fa) continue;
split(u,v);
merge(v,u);
dfs2(v,u);
//方法一
split(v,u);
merge(u,v);
//方法二：備份數組還原
}
return ;
}
dfs1(1,0);
dfs2(1,0);
- 類型二
1. 第一次掃描，任選一個節點為根，在“有根樹”上執行一次樹形dp。求出f[u]：以u為根的**子樹**……**（回溯后發生，自底向上的狀態轉移）**
轉移：$son_u→u$。
像正常樹形dp那樣轉移。
2. 第二次掃描，從剛才的根出發，對整棵樹深度優先遍歷。求出g[u]：以u為根的**整棵樹**……**（遞歸前發生，自頂向下的推導）**
轉移：$u→son_u$。
令$res=g[u]\ominus f[son_u]$，表示假如選點$son_u$為整棵樹的根，res為以u為根的子樹的值。
$g[son_u]←f[son_u]\oplus res$。
- 類型三
1. 第一次掃描自底向上，僅求出ans[1]的值。
2. 第二次掃描自頂向下，比較u和$son_u$的差異，必要時借助類型一求出差異的部分，用ans[u]和差異的部分求出$ans[son_u]$。
- 例題：積蓄程度
#include<bits/stdc++.h>
using namespace std;
const int N=2e5+5,M=N*2,INF=0x3f3f3f3f;
int t,n,root,ans;
int h[N],e[M],w[M],ne[M],idx;
int deg[N],d[N],f[N]; //deg[i]：節點i的度數；d[i]：以i為根的子樹，把i作為源點，從i出發流向子樹的最大流量；f[i]：把i作為源點，流向整個水系的最大流量；
void add(int a,int b,int c){
e[++idx]=b;
w[idx]=c;
ne[idx]=h[a];
h[a]=idx;
return ;
}
void dp(int u,int fa){ //回溯后發生，自底向上的狀態轉移
d[u]=0;
for(int i=h[u];i!=0;i=ne[i]){
int j=e[i];
if(j==fa) continue;
dp(j,u);
if(deg[j]==1) d[u]+=w[i];
else d[u]+=min(w[i],d[j]);
}
return ;
}
void dfs_f(int u,int fa){ //遞歸前發生，自頂向下的推導
for(int i=h[u];i!=0;i=ne[i]){
int j=e[i];
if(j==fa) continue;
if(deg[u]==1) f[j]=d[j]+w[i];
//f[u]是包含點j的，故由d[j]+f[u]->f[j]時要排除f[u]中點j的貢獻
else if(deg[j]==1) f[j]=min(w[i],f[u]-w[i]);
else f[j]=d[j]+min(w[i],f[u]-min(w[i],d[j]));
dfs_f(j,u);
}
return ;
}
int main(){
scanf("%d",&t);
while(t--){
idx=0,root=1,ans=0;
memset(deg,0,sizeof deg);
memset(h,0,sizeof h);
scanf("%d",&n);
for(int i=1;i<n;i++){
int a,b,c;
scanf("%d%d%d",&a,&b,&c);
add(a,b,c),add(b,a,c);
deg[a]++,deg[b]++;
}
dp(1,-1);
f[1]=d[1];
dfs_f(1,-1);
for(int i=1;i<=n;i++) ans=max(ans,f[i]);
printf("%d\n",ans);
}
return 0;
}
3.6.長鏈優化樹形dp\(O(N)\)
《數據結構·字符串和圖8.2.2.2.長鏈優化樹形dpO(N)》
3.7.基環樹dp
《圖論10.4.2.有向圖——基環樹dp》
3.8.笛卡爾樹dp
3.9.樹形dp的空間優化
先遍歷重兒子，重兒子回溯后再給當前節點申請空間，再遍歷輕兒子。并且每當兒子向當前節點合并信息后，把兒子的空間釋放?？梢杂胿ector動態申請釋放空間。
空間復雜度\(O((\log n)*其他維度)\)。
最壞情況是從當前節點到根節點的每條重鏈的鏈頂的父親開了O(其他維度)的空間，最多經過O(log n)條重鏈。
4.有向無環圖上的dp
4.1.有向無環圖上的dp
《圖論.3.有向無環圖上的dp》
4.2.借助有向無環圖的反圖做到\(O(樸素dp)\)預處理\(O(1)\)查詢
前提條件：
- 對于多個給定的x，求出在x的情況下同一個終點（DAG上同一個點）的dp值。
- 轉移方式具有交換律。\(e.g.\)對于計算概率，\(1*p_1*p_2=1*p_2*p_1\)。
- 轉移構成的 DAG的形態和邊（對于第i個狀態的轉移方式）是固定的，和x無關。
- 不同的x只是使得DAG上的出發點不同，但是無論是哪個出發點，初值都相同。
以上條件都常見于概率dp中。
考慮建出原 DAG 的反向 DAG，即如果原圖上 u → v 有權值為 w 的邊，新圖上有 v → u 權值為 w 的邊。
\(e.g.\)若原圖的轉移方程是\(f[i][j]=\sum\limits_{k=j}^n (f[i-1][k]*a^{k-j}*b)\)，則反圖上\(f[i][j]=\sum\limits_{k=0}^j (f[i+1][k]*a^{j-k}*b)\)（因為原圖是f[i][j]轉移到f[i+1][≤j]，所以反圖是f[i+1][≤j]轉移給f[i][j]）。
在反圖上令\(f[終點]=初值\)并\(O(樸素dp)\)預處理計算所有位置的 dp 值?，F在只需要\(O(1)\)調用反圖上初始化位置的 dp值就能得到在原圖從該初始化位置出發的終點dp值。
4.3.自動機上dp
前置知識
4.3.1.KMP
適用條件：有關字符串一匹一的dp問題。
\(f_{i,j}\)：s[1..i]的后綴已經匹配到t[1..j]的……。
轉移（由自己轉移到別人）：設val表示一次s[1..i]的后綴成功匹配到\(t[1..len_t]\)的貢獻。
-
若s[i+1]=t[j+1]，
- 若\(j+1==len_t\)，\(f_{i+1,ne[j+1]}←f_{i,j}+val\)。
- 否則，\(f_{i+1,j+1}←f_{i,j}\)。
-
若j≥1 ，\(f_{i,ne[j]}←f_{i,j}\)。
故第二維j需要倒序枚舉。
-
\(f_{i+1,0}←f_{i,j}\)。
邊界：\(f_{0,0}=0\)，其余均為\(-\infty\)。
時間復雜度\(O(len_slen_t)\)。
4.3.2.AC自動機
適用條件：有關字符串一匹多的dp問題。
\(f_{i,j}\)：走了i步，當前在AC自動機上的節點j的……。
轉移（由自己轉移到別人）：先建立AC自動機。轉移時枚舉當前的決策c，\(f_{i+1,tr[j].son[c]}←f_{i,j}\)。
邊界：\(f_{0,0}=0\)，其余均為\(-\infty\)。
注意：如果不進行拓撲排序，建立AC自動機時就需要額外加上下面的代碼：tr[tr[u].son[c]].ed|=tr[tr[tr[u].son[c]].fail].ed;//ed：當前節點是否是一個字符串的末尾
時間復雜度\(O(len_t\sum len_{s_i})\)。
5.環形dp與環形問題
5.1.破環成鏈轉化為線性dp
把環斷開成鏈，然后復制一倍接在末尾。
注意N開2倍?。?！
破環成鏈轉化為線性dp
下面以《環路運輸》為例：
把二元項拆成一元項，方便后面優化：設dis(i,j)=i-j，則\(A_i+A_j+dis(i,j)=(A_i+i)+(A_j-j)\)。此時可把只含i的項看作定值。
破環成鏈后，也就是對于每個i求滑動窗口長度在len/2（為保證只含i的項看作定值，dis(i,j)必須等于j-i，因此滑動窗口的長度是len/2）的權值\(A_j-j\)最大值，單調隊列做到線性求解。
int n,len,ans;
int a[N*2];
deque<int> ma;
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
a[i+n]=a[i];
}
len=n/2;
for(int i=1;i<=n*2;i++){
if(ma.size() && ma.front()<i-len) ma.pop_front();
ans=max(ans,i-ma.front()+a[ma.front()]+a[i]);
while(ma.size() && a[ma.back()]-ma.back()<=a[i]-i) ma.pop_back();
ma.push_back(i);
}
printf("%d\n",ans);
破環成鏈轉化為區間dp
區間右端點是到n*2終止！?。?/p>
下面以環形石子合并為例：
int n,nn,mi=INF,ma=-INF;
int w[N],sum[N];
int fi[N][N],fa[N][N];//fi[l][r]：把區間第l堆和第r堆石子合并成一堆需要消耗的最小體力
int main()
{
scanf("%d",&n);
nn=n<<1;
for(int i=1;i<=n;i++)
{
scanf("%d",&w[i]);
w[i+n]=w[i];
}
for(int i=1;i<=nn;i++) sum[i]=w[i]+sum[i-1];
memset(fi,0x3f,sizeof fi);
memset(fa,-0x3f,sizeof fa);
for(int l=1;l<=nn;l++) fi[l][l]=fa[l][l]=0;//邊界
for(int len=2;len<=n;len++)
for(int l=1;l+len-1<=nn/*注意這里是nn?。?！*/;l++)
{
int r=l+len-1;
for(int k=l;k<r;k++)
{
fi[l][r]=min(fi[l][r],fi[l][k]+fi[k+1][r]);
fa[l][r]=max(fa[l][r],fa[l][k]+fa[k+1][r]);
}
fi[l][r]+=sum[r]-sum[l-1];
fa[l][r]+=sum[r]-sum[l-1];
}
for(int l=1;l<=n;l++)
{
mi=min(mi,fi[l][l+n-1]);
ma=max(ma,fa[l][l+n-1]);
}
printf("%d\n%d\n",mi,ma);
return 0;
}
5.2.兩次dp，強制斷開相連
第一次dp破環成鏈，按照線性問題求解；第二次通過恰當的條件和賦值，保證計算出的狀態等價于把斷開的位置強制相連。
5.3.類環上兩點距離（距離）模型
求一個簡單環上任意兩點的最短距離
選擇環上任意一點rt。
預處理：s[u]：以s[rt]=0為起點，u所在環的距離前綴和。scir：u所在環的環長。
詢問：dis(x,y)=min(abs(s[x]-s[y]),scir-abs(s[x]-s[y]))。
//預處理
rt=1;
s[rt]=0;
for(int i=2;i<=n;i++) s[i]=s[i-1]+dis(i,i-1);
s[rt]=scir=s[n];
5.4.兩向擴展
環上固定一點st。\(f_{i,j}\)：已考慮st逆時針方向的i個點，順時針方向的j個點。
階段是i+j。然后枚舉i，j就自然確定了。
6.有后效性的dp
- 若dp的轉移是DAG：保證用到當前狀態時在DAG上所有該狀態的入邊已經轉移完全。
- 若dp的轉移有環：環形dp處理、分層圖跑dijkstra或spfa、高斯消元……。
一般采用遞推枚舉dp的轉移順序。
若不能直接遞推枚舉dp的轉移順序：記憶化搜索、分層圖跑dijkstra或spfa、dp套dp……。
6.1.概率dp
有時數學期望列出的式子各階段間無后效性，但是狀態轉移上具有后效性構成了環形，此時應用高斯消元優化dp。\(e.g.\)f[i][j]=calc(f[i][j-1],f[i][j+1],f[i-1][...])中i無后效性，j有后效性。
于是對于每一外層i（無后效性），其中內部維度j（有后效性）的轉移不再是普通的遞推，而是高斯消元解m元1次方程組。
《數學4.概率論》
6.2.分層圖最短路
《圖論4.3.分層圖最短路》
7.dp狀態優化和其他dp狀態
dp復雜度一般\(≥O(狀態數)\)。
優化狀態時思考哪些維度的狀態可以被其他維度的狀態計算出來，然后把這些狀態刪除，得到極小狀態集。
7.1.狀態壓縮dp
適用條件：“狀態”需要記錄“輪廓”的詳細信息，且數據范圍較小。
前置知識：《基礎知識1.6.狀態壓縮》
地圖類題目數據范圍給的是1≤n*m≤100，均需要把二維壓縮到一維：
//壓縮
int sets(int x,int y){
return (x-1)*m+y;
}
//還原
PII get(int state)
{
int x=(state-1)/m+1,y=(state-1)%m+1;//注意是state-1
return {x,y};
}
int state=sets(x,y);//壓縮
//還原
PII t=get(state);
x=t.first,y=t.second;
7.1.1.壓縮信息類
當n的范圍≤20時，可以用一個整數壓縮所有的信息：其中二進制表示下第i位是0表示第i個事件是false；是1表示true。
對于一個整數，逐一拆分成各個位上的1，逐一分析事件：
int log_2[1<<N];
for(LL i=0;i<n;i++) log_2[1<<i]=i;
for(int S=0;S<=limit;S++)
for(int s=S;s;s-=lowbit(s))
{
int pos=log_2[lowbit(s)];//第pos事件是true
}
求一個整數中1的個數：
《基礎算法1.3.統計a中 1 的個數離線預處理》
7.1.2.壓縮地圖類
特征：“填充網格圖形”，填充的圖形僅與相鄰的若干行有關，易按照“行”劃分階段。
核心
用二進制（0、1）表示狀態。
e.g.某一行有8塊土地，分別在第1、3、6塊土地上放炮，則用01串表示為10100100，將這個二進制轉換成十進制164存儲在state數組中。
步驟
預處理階段
- 存儲單個區域的不合法答案：存儲地圖mapp；
- 枚舉一行內的合法答案：檢查左右情況，并存入前驅state；
for循環階段
循環順序：階段 -> 狀態 -> 決策。
在state中枚舉逐行之間的情況。
for循環內部階段
- 檢查逐行之間的答案是否合法：檢查上下情況：
state[第x行]&state[第x-1行]； - 接著檢查單個區域內的答案是否合法：state與mapp進行與運算：
state[state_id]&mapp[row]； - 然后進行dp運算；
注意事項
- 狀態壓縮dp行數和列數最好從0開始
- 循環順序：階段 -> 狀態 -> 決策
- 循環階段i時，本題循環到n+1（從0開始）行，這樣最終答案自然在
f[n+1&1][0][0] - 例題1：炮兵陣地
#include<bits/stdc++.h>
using namespace std;
const int N=105,M=1<<10;
int n,m;
int mapp[N],cnt[M],f[2][M][M];
vector<int> state;
//檢查左右大炮情況
bool check(int a){
for(int i=0;i<m;i++) if((a>>i&1) && ((a>>i+1&1) || (a>>i+2&1))) return false;
return true;
}
//返回這個數的二進制表示下有多少個1
int count(int a){
int res=0;
while(a){
res+=a&1;
a>>=1;
}
return res;
}
int main(){
scanf("%d%d",&n,&m);
//存儲單個區域的不合法答案：存儲山地地圖
for(int i=0;i<n;i++) //行數從1開始易錯
for(int j=0;j<m;j++){
char a;
cin>>a;
/*
scanf是lj好吧
--------我是分割線--------
除了用cin，還可以像下面這樣寫：
char a=getchar();
while (!isalpha(a)) a=getchar();
*/
if(a=='H') mapp[i]+=1<<j;
}
//枚舉一行內的合法答案：檢查左右情況，并存入前驅state
for(int i=0;i<(1<<m);i++){
if(check(i)){
state.push_back(i);
cnt[i]=count(i);
}
}
for(int i=0;i<n+2;i++) //i：階段，本題循環到n+1（從0開始）行，這樣最終答案自然在f[n+1&1][0][0]
for(int j=0;j<state.size();j++)
for(int k=0;k<state.size();k++) //j（第i-1行的狀態）和k（第i行的狀態）：狀態
for(int l=0;l<state.size();l++){ //l（第i-2行的狀態）和i（第i-1行的狀態）：決策：由之前哪個狀態轉移過來
//檢查逐行之間的答案是否合法：檢查上下情況
//接著檢查單個區域內的答案是否合法：是否在山地上裝炮
//然后進行dp運算
int a=state[l],b=state[j],c=state[k]; //按照行數順序編排abc，依次為i-2、i-1和i
if((a&b) || (a&c) || (b&c)) continue;
if(c&mapp[i]) continue;
f[i&1][j][k]=max(f[i&1][j][k],f[i-1&1][l][j]+cnt[c]);
}
printf("%d\n",f[n+1&1][0][0]);
return 0;
}
-
例題2：拯救大兵瑞恩——有鑰匙的迷宮
BFS+狀態壓縮。
用狀態壓縮保存身上的鑰匙情況。二進制下第i位是1表示有第i種類型的鑰匙。
const int dx[]={1,-1,0,0};
const int dy[]={0,0,1,-1};
int n,m,p,k,s;
int g[N][N][N][N];//g[x1][y1][x2][y2]：從(x1,y1)到(x2,y2)所需要的鑰匙類型
int key[N][N];//key[x][y]：(x,y)放的鑰匙
int dis[N][N][1<<N];//dis[x][y][state]最小步數
struct Data
{
int x,y,state;
};
int bfs()
{
memset(dis,0x3f,sizeof dis);
queue<Data> q;
q.push({1,1,key[1][1]});
dis[1][1][key[1][1]]=0;
while(q.size())
{
auto t=q.front();
q.pop();
if(t.x==n && t.y==m) return dis[t.x][t.y][t.state];
for(int i=0;i<4;i++)
{
int x_ne=t.x+dx[i],y_ne=t.y+dy[i];
if(x_ne<=0 || x_ne>n || y_ne<=0 || y_ne>m) continue;
int &door=g[t.x][t.y][x_ne][y_ne];
if(door==0 || (door>=1 && !((t.state>>door)&1))) continue;
int state_ne=t.state|key[x_ne][y_ne];
if(dis[x_ne][y_ne][state_ne]>dis[t.x][t.y][t.state]+1)
{
dis[x_ne][y_ne][state_ne]=dis[t.x][t.y][t.state]+1;
q.push({x_ne,y_ne,state_ne});
}
}
}
return -1;
}
int main()
{
memset(g,-1,sizeof g);
scanf("%d%d%d",&n,&m,&p);
scanf("%d",&k);
while(k--)
{
int x1,y1,x2,y2,q;
scanf("%d%d%d%d%d",&x1,&y1,&x2,&y2,&q);
g[x1][y1][x2][y2]=q;
g[x2][y2][x1][y1]=q;
}
scanf("%d",&s);
while(s--)
{
int x,y,q;
scanf("%d%d%d",&x,&y,&q);
key[x][y]|=1<<q;
}
printf("%d\n",bfs());
return 0;
}
7.1.3.插頭dp
連通性狀態壓縮dp的一種。
特征：“填充網格圖形”，填充的圖形與整個網格有關，需要進一步提煉“輪廓”的特點。一般題目會給一個網格（棋盤），和連通性限制。
7.1.3.1.基礎知識——最短哈密頓距離\(O(2^N*N)\)
給定n個點，給定一個鄰接矩陣，求從0號節點到n-1號節點，不重不漏經過每個點恰好一次的路徑的最短距離。
狀態壓縮dp解決。
\(f[state][j]\)：所有從0走到j，走過的所有點是state（二進制下1代表走過）的路徑。
狀態轉移：走過的倒數第一個點是j，按走過的倒數第二個點劃分：\(f[state][j]=\min\limits_{k}^{state-(1<<j)>>k\&1} \{ f[state-(1<<j)][k]+a[k][j] \}\)
int n;
int a[N][N],f[M][N];
int main()
{
scanf("%d",&n);
for(int i=0;i<n;i++)
for(int j=0;j<n;j++)
scanf("%d",&a[i][j]);
memset(f,0x3f,sizeof f);
f[1][0]=0;
for(int state=0;state<(1<<n);state++)
//if(state&1)//這里還可以加個小剪枝：所有路徑肯定經過0號節點
for(int j=0;j<n;j++)
if((state>>j)&1)
for(int k=0;k<n;k++)
if(((state-(1<<j))>>k)&1)
f[state][j]=min(f[state][j],f[state-(1<<j)][k]+a[k][j]);
printf("%d\n",f[(1<<n)-1][n-1]);
return 0;
}
7.1.3.2.插頭dp
N*M棋盤問題當然可以用狀態壓縮dp解決，但是時間復雜度是\(O(2^{N*M}*N*M)\)，無法承受。這時我們可以用插頭dp解決。
7.1.3.2.1.回路
下面我們用一道模板題具體講解插頭dp：
-
模板題題面
給你一個 n×m 的棋盤，有的格子是障礙，問共有多少條回路滿足經過每個非障礙格子恰好一次。
![]()
如圖，n=m=4，(1,1),(1,2) 是障礙，共有 2 條滿足要求的回路。
輸入格式
第一行包含兩個整數 n,m。
接下來 n 行，每行包含一個長度為 m 的字符串，字符串中只包含
*和.，其中*表示障礙格子，.表示非障礙格子。輸出格式
輸出一個整數，表示滿足條件的回路數量。
數據范圍
2≤n,m≤12
輸入樣例：
4 4
**..
....
....
....
2
原題實際上是問棋盤上有多少種不同的Hamilton路徑。
通過觀察我們發現：每個格子有6種狀態（上下左右進，上下左右出，\(C_4^2=6\)）。因此，插頭dp以一個格子作為一個階段。
插頭dp一個格子一個格子枚舉時，我們發現，有用的信息是已枚舉的格子和未枚舉的格子的分界線——“輪廓”。我們只需要記錄邊界線的狀態，是否有邊伸出這個線（稱之為插頭）， 還要記錄伸出來的邊的連通性。輪廓線的狀態分為3種：沒有邊進出，有邊進（一個回路的左半邊），有邊出（一個回路的右半邊）。
\(f[i][j][state]\)：目前遞推到(i,j)且輪廓線狀態是state的所有方案數。
-
state輪廓線狀態的表示
![]()
括號表示法
優點：效率比最小表示法高，不用像最小表示法那樣維護連通信息，可以借助四進制壓縮信息。
缺點：適用題目必須有以下性質：1.整個網格構成一個回路；2.兩兩配對，邊界上有一個邊進就有一個邊出；3.任意路徑不相交。
本題有上述的3個性質，因此每一個“進邊（一個回路的左半邊）”用“1”表示，“出邊（一個回路的右半邊）”用“2”表示，沒有邊進出用“0”表示。這就好像一個括號序列，“1”和“2”之間兩兩配對。
\(e.g.\)上面的圖的最小表示法是101022。
于是我們可以類似二進制那樣用四進制壓縮信息。（本質上是用兩位的二進制表示一位的四進制，四進制更方便因此我們不用三進制）
大部分插頭dp困難的地方在于狀態轉移。大部分插頭dp的狀態轉移需要分類討論。
-
狀態轉移
![]()
狀態的轉移實際上是上圖的實線的分界線的狀態轉移到虛線的分界線的狀態。
由于插頭dp是從左到右，從上到下一個格子一個格子枚舉，因此當前枚舉的格子，分界線一定是
_|—形，我們設當前枚舉的格子左邊一個分界線（第一列的格子仍然視為左邊有一個分界線）的狀態是x，上邊是y：（截圖自墨染空的題解）
畫圖非常方便理解！
技巧：
-
我們只會用到上一個階段的信息，因此用滾動數組優化。
-
即使用四進制壓縮信息，該四進制數仍然很大，需要使用哈希。
注意如果使用vector而不使用哈希存每一階段的狀態，因為同一階段轉移到相同的狀態無法合并，所以每一階段結束時需要多一個\(O(\log)\)排序并合并相同的狀態。
-
類似于狀態壓縮dp，用數組存儲有效狀態。
-
如果給定的n*m網格n<m，交換n、m，用四進制壓縮較小的位數。
-
不要忘記開
long long哦～
大部分插頭dp解題方法：根據“網格”知道這是插頭dp+背下面的模板+設計輪廓線狀態+畫圖分析狀態轉移。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const int N=5e4+10,M=N*2+7;//M：模數，>=2~3N的幸運數字
int n,m;
int edx,edy; ////存下最后一個不是障礙物的點的坐標，方便確定在哪里將回路閉合是合法的
LL ans;
bool mapp[20][20]; //true表示能走（邊界初始是false所以不能走）
int q[2][N],cnt[2]; //q[bool][idx]：滾動數組，通過存儲第idx的哈希值來記錄哪些狀態供轉移；cnt[bool]：滾動樹組，存儲上一層有多少個狀態，同時也充當本層的“idx”
int h[2][M]; //h[bool][hash]滾動數組，存儲原狀態
LL v[2][M]; //v[bool][hash]：滾動數組，存儲哈希對應的原狀態的方案數
//哈希（開源尋址法）
int find(int cur,int state)
{
int t=state%M;
while(h[cur][t]!=-1 && h[cur][t]!=state)
{
t++;
if(t==M) t=0;
}
return t;
}
void insert(int cur,int state,LL w)
{
int t=find(cur,state);
if(h[cur][t]==-1)
{
q[cur][++cnt[cur]]=t;
h[cur][t]=state;
v[cur][t]=w;
}
else v[cur][t]+=w;//如果是求方案數則相加，如果是求最值則取最值
return ;
}
//四進制：本質上是用兩位的二進制表示一位的四進制
//四進制下右移K位就是二進制下右移2*K位
int get(int state,int k)//求第k個格子的狀態，四進制的第k位數字
{
return (state>>(k*2))&3; //&3：類似于二進制，消除最高位只保留最后2位
}
int sets(int v,int k)//構造四進制的第k位數字為v的數
{
return v*(1<<(k*2));
}
int main()
{
scanf("%d%d",&n,&m);
for(int i=1;i<=n;i++)
{
char str[20];
scanf("%s",str+1);
for(int j=1;j<=m;j++)
if(str[j]=='.') //不斷覆蓋，覆蓋到最后剩下的就是真正的最后一個可以放的格子
{
mapp[i][j]=true;
edx=i,edy=j;
}
}
memset(h,-1,sizeof h);
int cur=0;
insert(cur,0,1); //初始界限狀態是0，什么都不連（0）的方案數是1
for(int i=1;i<=n;i++)
{
for(int idx=1;idx<=cnt[cur];idx++) h[cur][q[cur][idx]]<<=2;//換行操作，把上一行最后一列的狀態的最高位的0移到最低位得到每一行第一列的狀態
for(int j=1;j<=m;j++)//階段（一個格子就是一個階段）+狀態，一個網格一個網格枚舉
{
//每一輪都是新的界限
int last=cur;
cur^=1,cnt[cur]=0;
memset(h[cur],-1,sizeof h[cur]);
for(int idx=1;idx<=cnt[last];idx++)
{
int state=h[last][q[last][idx]];
LL w=v[last][q[last][idx]];
int x=get(state,j-1),y=get(state,j);
//分類討論
//除了輪廓線下標從0開始（0-m,狀態壓縮），其余都是從1開始
//畫圖發現，當前枚舉方塊(i,j)是，拐彎形狀的輪廓線拐點在(i,j)
//(i,j)左側邊界編號應該是j-1,上邊界編號是j
if(!mapp[i][j])
{
if(x==0 && y==0) insert(cur,state,w);
//如果沒有插頭，這是合法狀態，加入哈希表中，權值不變
//else 不合法
}
else if(x==0 && y==0)
{
//insert(cur,state,w);//如果不要求走完所有的格子，則加入這行代碼
if(mapp[i+1][j] && mapp[i][j+1])
{
state+=sets(1,j-1)+sets(2,j);
insert(cur,state,w);
}
//一根線上靠左的（一個回路的左半邊）是1，靠右的（一個回路的右半邊）是2
}
else if(x==0 && y!=0)
{
//注意下面的順序不能顛倒
if(mapp[i][j+1]) insert(cur,state,w);
if(mapp[i+1][j])
{
state+=sets(y,j-1)-sets(y,j);
insert(cur,state,w);
}
}
else if(x!=0 && y==0)
{
if(mapp[i+1][j]) insert(cur,state,w);
if(mapp[i][j+1])
{
state+=sets(x,j)-sets(x,j-1);
insert(cur,state,w);
}
}
else if(x==1 && y==1)
{
for(int u=j+1,tot=1;;u++)
{
int z=get(state,u);
if(z==1) tot++;
else if(z==2)
{
tot--;
if(tot==0)
{
state+=-sets(x,j-1)-sets(y,j)-sets(1,u);
insert(cur,state,w);
break;
}
}
}
}
//向右找到Y對應的2，改成1
//這種尋找方法就是括號匹配的尋找方法，可以過濾掉中間成對的括號
else if(x==2 && y==2)
{
for(int u=j-2,tot=1;;u--)
{
int z=get(state,u);
if(z==2) tot++;
else if(z==1)
{
tot--;
if(tot==0)
{
state+=-sets(x,j-1)-sets(y,j)+sets(1,u);
insert(cur,state,w);
break;
}
}
}
}
else if(x==2 && y==1) //把它們連起來
{
state+=-sets(x,j-1)-sets(y,j);
insert(cur,state,w);
}
else if(i==edx && j==edy) ans+=w;
//else if(state==set(x,j-1)+set(y,j)) ans+=w;如果不要求走完所有的格子，即edx,edy是未定的，則只有當輪廓線的當前位置x=1,y=2且其他位置都是0時，把貢獻計入答案
}
}
}
printf("%lld\n",ans);
return 0;
}
7.1.3.2.2.連通塊
類似于回路。
-
state輪廓線狀態的表示
不同于回路，連通塊的輪廓線是由格子組成的。
![]()
最小表示法
優點：適用范圍廣。
缺點：要維護連通信息：每條進出的邊屬于哪個連通塊。
對于未標記的邊標記一個最小的數字（同一個連通塊的標記相同，沒有邊進出標記0）。
\(e.g.\)若上面的圖1屬于一個連通塊，2和3屬于一個連通塊，則最小表示法是0122。
通常數據范圍列數不會超過10，因此使用一個8進制數表示狀態
為狀態轉移方便，轉移過程中不要求狀態是最小表示的，在插入狀態時才調用update()函數把其轉化為最小表示的。
注意非插入狀態時不可輕易把state轉化為最小表示的，否則x,y的真實值會改變
//在調用insert傳入state時使用
//先合并連通塊mi,ma（除了mi,ma編號為-1或0），然后返回state的最小表示
int update(int state,int mi,int ma)
{
int idx=0,s=0;
memset(vis,0,sizeof vis);
for(int i=1;i<=n;i++)
{
int x=get(state,i);
if(!x) continue; //一定要放在第一位，防止mi=0的干擾
if(x==mi) x=ma;
if(!vis[x]) vis[x]=++idx;
s+=sett(vis[x],i);
}
return s;
}
//返回state有多少個連通塊
int count(int state)
{
int idx=0;
memset(vis,0,sizeof vis);
for(int i=1;i<=n;i++)
{
int x=get(state,i);
if(!x) continue;
if(!vis[x]) vis[x]=++idx;
}
return idx;
}
-
狀態轉移
狀態的轉移實際上是上圖的實線的輪廓線的狀態轉移到虛線的輪廓線的狀態。
由上圖得：輪廓線一定是
_|—形，我們設當前枚舉的格子左邊一個輪廓線（第一列的格子仍然視為左邊有一個輪廓線。不同于回路，連通塊不需要換行）的狀態是x，上邊是y：枚舉完當前的格子后，y將會與外界“隔離”。
-
不選擇當前的格子：y←0。
注意，如果題目要求最終只能有一個連通塊，那么只有 不選擇當前格子后的輪廓線的連通塊數 等于 之前的輪廓線的連通塊數 時，才可以不選擇當前的格子。
-
選擇當前的格子
-
若xy0，當前的格子形成一個新的連通塊。由于列數的數據范圍通常會使得輪廓線的連通塊數小于7，因此7是一個未使用的編號，暫時給當前的連通塊編號為7：y←7。到后面插入狀態求最小表示法
update()再做調整。 -
若x0，y≠0或x≠0,y0，當前格子與原有的連通塊聯通。
若x≠0,y≠0，當前格子與2個連通塊聯通，2個連通塊合并為1個連通塊。
上面的轉移可使用一行代碼一起實現：
insert(cur,update(state-sett(y,j)+sett(max(x,y),j),min(x,y),max(x,y)),w+a[i][j]);
-
畫圖非常方便理解！
-
-
例題的代碼
int n,ans=-1e9;
int a[10][10];
int q[2][N],cnt[2];
int h[2][M],v[2][M];
int vis[8];
int get(int state,int k)
{
return (state>>k*3)&7;
}
int sett(int v,int k)
{
return v*(1<<k*3);
}
//在調用insert傳入state時使用
//先合并連通塊mi,ma（除了mi,ma編號為-1或0），然后返回state的最小表示
int update(int state,int mi,int ma)
{
int idx=0,s=0;
memset(vis,0,sizeof vis);
for(int i=1;i<=n;i++)
{
int x=get(state,i);
if(!x) continue; //一定要放在第一位，防止mi=0的干擾
if(x==mi) x=ma;
if(!vis[x]) vis[x]=++idx;
s+=sett(vis[x],i);
}
return s;
}
//返回state有多少個連通塊
int count(int state)
{
int idx=0;
memset(vis,0,sizeof vis);
for(int i=1;i<=n;i++)
{
int x=get(state,i);
if(!x) continue;
if(!vis[x]) vis[x]=++idx;
}
return idx;
}
int find(int cur,int state)
{
int t=state%M;
while(h[cur][t]!=-1 && h[cur][t]!=state)
{
t++;
if(t==M) t=0;
}
return t;
}
void insert(int cur,int state,int w)
{
int t=find(cur,state);
if(h[cur][t]==-1)
{
q[cur][++cnt[cur]]=t;
h[cur][t]=state;
v[cur][t]=w;
}
else v[cur][t]=max(v[cur][t],w);
if(count(state)==1) ans=max(ans,w);
return ;
}
int main()
{
scanf("%d",&n);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
scanf("%d",&a[i][j]);
int cur=0;
memset(h[cur],-1,sizeof h[cur]);
insert(cur,0,0);
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
{
int last=cur;
cur^=1,cnt[cur]=0;
memset(h[cur],-1,sizeof h[cur]);
for(int idx=1;idx<=cnt[last];idx++)
{
int state=h[last][q[last][idx]],w=v[last][q[last][idx]];
int x=get(state,j-1),y=get(state,j);
int res=count(state);
state=state-sett(y,j); //這里不可直接加update，否則x,y的真實值會改變
if(count(state)==res) insert(cur,update(state,-1,-1),w);
w=w+a[i][j];
if(!x && !y) insert(cur,update(state+sett(7,j),-1,-1),w);
else insert(cur,update(state+sett(max(x,y),j),min(x,y),max(x,y)),w);
}
}
printf("%d\n",ans);
return 0;
}
7.2.倍增優化dp
適用條件：階段的遞推形式。
-
預處理 dp
\(f[k][...]\)：...走了2^k步（一般是階段）。
先計算f[0][...]；
再dp
f[k][...]=f[k-1][...]（先走2^k-1步）+f[k-1][...f[k-1][...]...]（再走2^k-1步）； -
二進制拼湊（兩種代碼）
int p=i;
for(int k=30;k>=0;k--){
if(p+f[p-1][k]<=N){
p+=f[p-1][k];
}
}
//要先預處理前綴和s
int p=1,k=0,sum=0;
while(p){
if(sum+s[k+p]-s[k]<=M){
sum+=s[k+p]-s[k];
k+=p;
if(k>N) break;
p*=2;
}
else p/=2;
}
7.3.數位DP
給定若干個要求和一個正整數x，求小于等于x的正整數中滿足題目要求的數的個數。
為數不多可以套模板無腦切題的dp……（當然有些題目還是不能套模板必須思考的）
7.3.1.記憶化搜索寫法
模板
在多組測試數據中，數組a會改變，從而影響到限定limit。因此：
-
要么在dp數組f中不加入limit并在dp過程中進行!limit的判斷，時間復雜度是O(max(數位dp狀態數轉移的復雜度,T位數*轉移的復雜度))。
“T位數轉移的復雜度”：因為只有當一直i==up時limit為真，所以只有位數個狀態是每組測試數據都要計算的。
-
要么在dp數組f中加入limit并在每次調用
calc()時初始化dp數組f，時間復雜度是O(T數位dp狀態數轉移的復雜度)。
下面采用的寫法是在dp數組f中不加入limit并在dp過程中進行!limit的判斷。
int a[N],len;
ll f[N][/*可選參數*/][/*可選限定*/]; //f[pos][可選參數][可選限定]：在沒有limit限定的情況下，當前從高位到低位考慮到第pos位且前面……且限定情況是……的方案數
ll dp(int pos,/*可選參數*/,bool limit,/*可選限定*/)
{
if(pos==0) return /*合法條件*/ ? 1 : 0;
if(!limit && f[pos][/*可選參數*/][/*可選限定*/]!=-1) return f[pos][/*可選參數*/][/*可選限定*/];
ll res=0;
int up=limit ? a[pos] : /*進制-1（無限制位上的可填的最大的數）*/;
for(int i=0;i<=up;i++)
{
if(/*不合法條件*/) continue;
res+=dp(pos-1,/*可選參數*/,limit && i==up,/*可選限定*/);
}
return !limit ? (f[pos][/*可選參數*/][/*可選限定*/]=res) : res;
}
ll calc(ll x)
{
len=0;//！?。∽⒁獬跏蓟。。? //無需初始化f
while(x) a[++len]=x%/*進制*/,x/=/*進制*/;
return dp(len,0,true,true);//調用，初始條件
}
memset(f,-1,sizeof f);//?。?！注意在這里初始化?。。?int t;
cin>>t;
while(t--)
{
ll x;
cin>>x;
cout<<calc(x)<<endl;
}
技巧
- 空間換時間：在dp數組f中加入limit，從而在dp過程中無需進行!limit的判斷。注意在每次調用
calc()時需要初始化dp數組f，因此不太適用于多組測試數據。
ll f[N][/*可選參數*/][2][/*可選限定*/]; //f[pos][可選參數][limit][可選限定]：當前從高位到低位考慮到第pos位且前面……且限定情況是……的方案數
ll dp(int pos,/*可選參數*/,bool limit,/*可選限定*/)
{
//……
ll &res=f[pos][/*可選參數*/][limit][/*可選限定*/];
if(res!=-1) return res;
res=0;
//……
return res;
}
ll calc(ll x)
{
memset(f,-1,sizeof f);//！??！注意在每次調用calc()時需要初始化dp數組f?。?！
//……
}
-
減法借位
\(e.g.\)給定n，求1~n中x滿足條件1且n-x滿足條件2的x的個數。
x的上界就是n，而式子又出現減法，當枚舉某一數位時\(n_{p_i}-x_{p_i}\)時可能為負數，需要向高位借位，因此從低向高枚舉數位。記憶化搜索多傳一個變量borrow：當前的數位有沒有被上一個低數位借位。
- 最高位不能向它的高位借位。
- 枚舉當前的數位時，若枚舉的x>n則一定會向最高位的高位借位而被上面特判掉。因此這里不用考慮當前數位可以填數的限定
- 枚舉當前的數位時，若已被低位借位，記得減1。
- 若枚舉當前的數位的值為負數，向高位借位。
int f[N][2]; //f[pos][bor]：當前從低位到高位考慮到第pos位，當前的數位有沒有被上一個低數位借位且滿足條件的個數
int dp(int pos,bool bor)
{
if(pos>len) return !bor; //最高位不能被借位
int &res=f[pos][bor];
if(res!=-1) return res;
res=0;
for(int i=0;i<=9;i++) //x的上界就是n，若枚舉的x>n則一定會向最高位的高位借位而被上面特判掉。因此這里不用考慮當前數位可以填數的限定
{
int u1=i,u2=n[pos]-i-bor; //-bor：被低位借位
bool b=false;
if(u2<0) u2+=10,b=true; //若為負數，則向高位借位
//abaabaaba
res+=dp(pos+1,b);
}
return res;
}
7.3.1.1.calc函數
作用：1.數→該數的每個數位的上界數組a[]；2.返回1～x中有多少個滿足要求的數。
len: 數位長度，一般根據這個來確定數組范圍
\(a_i\): 每個數位的上界
在calc函數中實現。
$e.g.$123456→
| 數組下標 | 1 | 2 | 3 | 4 | 5 | len=6 |
| 數位數字 | 6 | 5 | 4 | 3 | 2 | 1 |
調用記憶化搜索時從len開始，繼續遞歸pos-1，這樣可實現求原數時令val*10+i。
7.3.1.2.dp函數
變量 res 來記錄答案，初始化一般為 0。
變量 up 表示當前位上的可填的最大的數。
7.3.1.2.1.必選參數與必選限定：
-
pos: 表示數字的位數
根據題目的數字構造性質來選擇 dp 順序，一般選擇從最高位到最低位的順序。初始從 len 開始的話，邊界條件應該是 pos=0，有限定的情況下當前的最高位可以填的最大的數應該是 a_{pos}，往下遞歸時令 pos?1。
這樣可實現求原數時令val*10+i。
-
limit: 當前的最高位可以填數的限定（無限制的話(limit==false) 0～9隨便填，否則只能填到a[pos]，因為大小不能超過給定的數）
如果搜索到a1?apos?an，給定的數x的數位為a1?ak?an，那么我們必須對接下來搜索的數加以限制，也就是不能超過區間右端點 R，所以要引入limit這個參數：如果limit=1有限制，那么最高位數up≤apos+1，否則無限制，那么up=9（十進制下）這也就是確定搜索位數上界的語句limit ? a[pos] : 9;
如果 limit=1 且已經取到了能取到的最高位時 (apos=ak)，那么下一個 limit=1；
如果 limit=1 且沒有取到能取到的最高位時 (apos<ak)，那么下一個 limit=0；
如果 limit=0，那么下一個limit=0，因為前一位沒有限制后一位必定沒有限制。
所以我們可以把這3種情況合成一個語句進行下一次搜索：limit && i == up
(i為當前枚舉的數字)在多組測試數據中，數組a會改變，從而影響到限定limit。因此要么在dp數組f中不加入limit并在dp過程中進行!limit的判斷，時間復雜度是O(max(數位dp狀態數轉移的復雜度,Tlog W轉移的復雜度))；要么在dp數組f中加入limit并在每次調用
calc()時初始化dp數組f，時間復雜度是O(T數位dp狀態數*轉移的復雜度)。
7.3.1.2.2.可選參數
根據題意選擇。
dp數組每個維度包含pos和可選參數。
這里參數的最大值等于dp數組的大小上界，因此涉及到“原數...不是...的整數倍”遞歸時要記得參數取模。
pre和cnt大部分情況需要配合前導零限定lead
-
pre:表示上一個數是多少
有些題目會用到前面的數
- 數字中不能含有4和62
int dfs(int pos,int pre,bool limit)
{
if(pos==0) return 1;
if(!limit && dp[pos][pre]!=-1) return dp[pos][pre];
int res=0,up=limit ? a[pos] : 9;
for(int i=0;i<=up;i++)
{
if(i==4 || (i==2 && pre==6)) continue;
res+=dfs(pos-1,i,limit && i==up);
}
return limit ? res : (dp[pos][pre]=res);
}
return dfs(len,0,true);
-
任意相鄰兩個數位上的數字之差至少為 2
必須填一個abs(pre - i) ≥ 2的數才能滿足條件繼續搜索下去，且初始條件參數 pre 必須填一個 ≤?2 的數來保證可以搜索下去。因此此題要限定前導零！
int dfs(int pos,int pre,bool lead,bool limit)
{
if(!pos) return 1;
if(!lead && !limit && dp[pos][pre]!=-1) return dp[pos][pre];
int res=0,up=limit ? a[pos] : 9;
for(int i=0;i<=up;i++)
{
if(abs(i-pre)<2) continue;
if(lead && i==0) res+=dfs(pos-1,-2,lead && i==0,limit && i==up);
else res+=dfs(pos-1,i,lead && i==0,limit && i==up);
}
return !lead && !limit ? (dp[pos][pre]=res) : res;
}
return dfs(len,-2,true,true);
-
數位從高到低非嚴格單調遞增$e.g.$123、446
前導零不影響，不需要lead。
int dfs(int pos,int pre,bool limit)
{
if(!pos) return 1;
if(!limit && dp[pos][pre]!=-1) return dp[pos][pre];
int res=0,up=limit ? num[pos] : 9;
for(int i=0;i<=up;i++)
{
if(i<pre) continue;
res+=dfs(pos-1,i,limit && i==up);
}
return limit ? res : (dp[pos][pre]=res);
}
return dfs(len,0,true);
-
cnt:某個數字出現的次數
有些題目會出現某個數字出現次數的條件。
-
B進制下，數位上恰好出現K個1，其他均為0。
若填某個數位為1前已經有k個1了，就
continue。
-
int dp[N][N]; //dp[pos][cnt]：第pos位且前面填了cnt個1的方案數
int dfs(int pos,int cnt,bool limit)
{
if(!pos) return cnt==k;
if(!limit && dp[pos][cnt]!=-1) return dp[pos][cnt];
int res=0,up=limit ? a[pos] : b-1;
for(int i=0;i<=min(up,1);i++)
{
if(i==1 && cnt==k) continue;
res+=dfs(pos-1,cnt+(i==1),limit && i==up);
}
return limit ? res : (dp[pos][cnt]=res);
}
return dfs(len,0,true);
-
sum:搜索到當前所有數位上的數字之和
有些題目會出現數位之和的條件。
加和乘運算之間可以任意模一個相同的數。
- 數位之和不是x的整數倍
int dfs(int sum)
{
if(pos==0) return sum!=0 ? 1 : 0;
for(int i=0;i<=up;i++) res+=dfs((sum+i)%x);
}
-
val:搜索到當前的原數
求原數時令val*10+i。
- 原數不是x的倍數
int dfs(int val)
{
if(pos==0) return val!=0 ? 1 : 0;
for(int i=0;i<=up;i++) res+=dfs((val*10+i)%x);
}
-
十進制原數能夠被它的數位之和整除
由于模數（數位之和）在遞歸到達邊界前不能確定，因此在calc函數中調用dfs前枚舉模數（1～進制9*len）
int dfs(int pos,int val,int sum,bool limit)
{
if(pos==0) return val==0 && sum==mod ? 1 : 0;
if(!limit && dp[pos][val][sum]!=-1) return dp[pos][val][sum];
int res=0,up=limit ? a[pos] : 9;
for(int i=0;i<=up;i++) res+=dfs(pos-1,(val*10+i)%mod,sum+i,limit && i==up);
return limit ? res : (dp[pos][val][sum]=res);
}
int calc(int x)
{
int res=0;
len=0;
while(x) a[++len]=x%10,x/=10;
for(mod=1;mod<=9*len;mod++)
{
memset(dp,-1,sizeof dp);//！??！記得初始化?。? res+=dfs(len,0,0,true);
}
return res;
}
-
key:布爾參數
注：它也要作為dp數組的一個維度。
- 數位中但凡出現連續3個6。e.g.666、6663、6666。
LL dfs(LL pos,LL pre,bool key,bool limit)
{
if(pos==0) return key;
if(!limit && dp[pos][pre][key]!=-1) return dp[pos][pre][key];
LL res=0,up=limit ? a[pos] : 9;
for(int i=0;i<=up;i++)
{
if(i==6)
{
if(pre>=2) res+=dfs(pos-1,pre+1,true,limit && i==up);
else res+=dfs(pos-1,pre+1,key,limit && i==up);
}
else res+=dfs(pos-1,0,key,limit && i==up);
}
return limit ? res : (dp[pos][pre][key]=res);
}
dfs(len,0,false,true);
- 不體現在數組中的參數
- 數位中某一位不是x
int dfs()
{
for(int i=0;i<=up;i++)
{
if(i==x) continue;
res+=dfs();
}
}
7.3.1.2.3.可選限定
根據題意選擇。
-
lead:前導零是否存在，lead=true存在前導零，否則不存在
一般來說有些題目不加限制前導零會影響數字結構（尤其是涉及到參數pre），所以 lead 是一個很重要的參數。
如果 lead=1 且當前位為 0，那么說明當前位是前導 0，繼續搜索 pos+1，其他條件不變。
如果 lead=1 且當前位不為 0，那么說明當前位是最高位，繼續搜索 pos+1，條件變動。
如果 lead=0，則不需要操作。
7.3.1.3.主函數
根據題目要求寫。
-
求[l,r]中滿足要求的數的個數
calc()函數返回1～x中有多少個滿足要求的數。用類似于前綴和的思想ans=calc(r)-calc(l-1)。
int main(){
scanf("%d%d",&l,&r);
printf("%d\n",calc(r)-calc(l-1));
return 0;
}
-
求[l,r]中滿足要求的數的個數、和、平方和
我們還是先用 數位DP-記憶化搜索 求解問題的方式去思考，如何在求解的過程中 記錄/合并信息
既然是 搜索，不妨先用 分治的思想，把 大問題集合 劃分成多個 子問題集合，最后再進行 合并
假設 我們當前已經搜出了 pos-1 層的信息，現在向上 回溯，如何把該信息合并到 大集合 中呢？
考慮在 搜索 時，如何合并多條搜索分支 回溯 的 平方和信息
\(∑_i(aA_i)^2=∑_i(a×10^{p?1}+A_i)^2=\)\((∑_i1)×(a×10 ^{p?1})^2+2×(a×10_{ p?1})×∑_iA_i+∑_iA_i^2\)
根據上述 遞推式 可知，我們枚舉當前數位填 aa 以后下沉 搜索，然后 回溯時 需要傳遞的 信息 有:能接在 a 以后的數字 Ai 的個數 ∑i1
能接在 a 以后的數字 Ai 的總和 ∑iAi
能接在 a 以后的數字 Ai 的平方和 \(∑_iA_i^2\)于是我們可以把 記憶化搜索 的 屬性值 開成 3維，分別記錄這三個值： s0, s1, s2
回溯的時候，分別對這三個值進行合并即可
上述遞推式給出了 s2 的合并， s1 的合并如下：
\(∑_i(aAi)=∑_i(a×10^{p?1}+A_i)=\)\((∑_i1)×(a×10 ^{p?1})+∑_iA_i\)
s0 的合并就是直接個數相加即可。
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
const LL N=20,MOD=1e9+7;
LL T,l,r;
LL pow_10[N]; //預處理10的冪次
LL a[N],len;
struct DP
{
LL s0,s1,s2;
void operator += (const DP &t)
{
s2=(s2+t.s2)%MOD;
s1=(s1+t.s1)%MOD;
s0=(s0+t.s0)%MOD;
}
}dp[N][N][N]; //dp[pos][sum][val]
DP dfs(int pos,int sum,int val,bool limit)
{
if(pos==0)
{
if(sum!=0 && val!=0) return (DP){1,0,0};
else return (DP){0,0,0};
}
if(!limit && dp[pos][sum][val].s0!=-1) return dp[pos][sum][val];
DP res={0,0,0};
int up=limit ? a[pos] : 9;
for(int i=0;i<=up;i++)
{
if(i==7) continue;
DP t=dfs(pos-1,(sum+i)%7,(val*10+i)%7,limit && i==up);
LL k=i*pow_10[pos-1]%MOD;
t.s2=((t.s2+t.s1*2%MOD*k%MOD)%MOD+t.s0*k%MOD*k%MOD)%MOD;
t.s1=(t.s1+t.s0*k%MOD)%MOD;
res+=t;
}
return limit ? res : (dp[pos][sum][val]=res);
}
LL calc(LL x)
{
memset(dp,-1,sizeof dp);
len=0;
while(x) a[++len]=x%10,x/=10;
return dfs(len,0,0,true).s2;
}
int main()
{
pow_10[0]=1;
for(int i=1;i<20;i++) pow_10[i]=pow_10[i-1]*10%MOD;
scanf("%lld",&T);
while(T--)
{
scanf("%lld%lld",&l,&r);
printf("%lld\n",((calc(r)-calc(l-1))%MOD+MOD)%MOD); //!!!
}
return 0;
}
-
求[l,r]中滿足要求的數中某數碼的出現次數
在母題的基礎上，選擇可選參數 cnt（當前已有的某數碼的個數），在 dp 函數中當 pos==0 且滿足題目要求時返回 cnt。
-
求第rk小的滿足要求的數
方法一
一般從高位到低位考慮：
對于每一位，從0到 進制-1 考慮填入：
對于每一個考慮填入的數，借助數位dp（在參數限定下求正整數中有多少個滿足題目要求的數，與模板基本相同。無需calc函數和limit限定。直接調用dp函數，每次調用不要初始化dp數組）計算在當前填入情況下（在調用dp函數時根據當前填入情況填寫對應的參數限定）后面的方案數： 若方案數小于rk，則令rk-=方案數，考慮下一個數。 若方案數大于等于rk，則當前考慮的位填入當前考慮的數，考慮下一位。因為dp采用記憶化，所以在多組測試數據下，時間復雜度為O(max(數位dp狀態數轉移的復雜度,T位數*進制))。
//無需limit限定
int t;
ll rk,x;
ll f[N][/*可選參數*/][/*可選限定*/]; //f[pos][可選參數][可選限定]：在沒有limit限定的情況下，當前從高位到低位考慮到第pos位且前面……且限定情況是……的方案數
ll dp(int pos,/*可選參數*/,/*可選限定*/) //在參數限定下求正整數中有多少個滿足題目要求的數，與模板基本相同
{
if(pos==0) return /*合法條件*/ ? 1 : 0;
ll &res=f[pos][/*可選參數*/][/*可選限定*/];
if(res!=-1) return res;
res=0;
for(int i=0;i<=/*進制-1*/;i++)
{
if(/*不合法條件*/) continue;
res+=dp(pos-1,/*可選參數*/,/*可選限定*/);
}
return res;
}
memset(f,-1,sizeof f);//注意在這里初始化
scanf("%d",&t);
while(t--)
{
x=0;
scanf("%lld",&rk);
int pos=/*可能的最高位數*/,/*可選參數*/;bool /*可選限定*/; //答案x的參數限定
while(pos>=1)
{
x*=/*進制*/;
for(int i=0;i<=/*進制-1*/;i++)
{
ll res=dp(pos-1,/*可選參數*/,/*可選限定*/); //根據當前填入情況填寫對應的參數限定
if(res<rk) rk-=res;
else //第pos位填入i
{
x+=i;
/*根據第pos位填入i，更新答案x的參數限定
……
*/
break;
}
}
}
printf("%lld\n",x);
}
方法二
二分查找。
l=1,r=MAX;calc(mid)≥rk;
在多組測試數據下，寫法“dp數組f中不加入limit并在dp過程中進行!limit的判斷”的時間復雜度是O(max(數位dp狀態數轉移的復雜度,Tlog MAX位數轉移的復雜度))，寫法“在dp數組f中加入limit并在每次調用calc()時初始化dp數組f”的時間復雜度是O(Tlog MAX數位dp狀態數*轉移的復雜度)。
scanf("%lld",&rk);
ll l=1,r=MAX;
while(l<r)
{
ll mid=(l+r)>>1;
if(calc(mid)>=rk) r=mid;
else l=mid+1;
}
printf("%lld\n",l);
-
求[l,r]中f(x)的最值
下面的方法要求f(x)較小。下面以最大值為例。
從f(x)的上界到下界枚舉key，數位dp計算[l,r]中滿足f(x)等于key的數的個數，如果大于等于1則直接結束，答案是這個key。
7.3.2.循環寫法
模板
常用于二進制數計數。
時間復雜度O(T二進制位數轉移的復雜度)。
for(int k=bit;k>=0;k--)
{
if((x>>k)&1)//當前原數的最高位是1
{
/*當前最高位填0，后面的任意填，直接計算
……
ans+=calc();
*/
/*當前最高位填1，繼續迭代
……
*/
}
else//當前原數的最高位是0，只能填0，繼續迭代
{
/*
……
*/
}
//邊界情況：填的數就是x
if(k==0)
{
if(check(x)) ans++;
}
}
推論dp
對于小于（大于）等于x的二進制數x'，一種dp狀態設計：f_k：在小于（大于）等于x的前提下，從高到低的第一位k滿足在第k位下x為1并且x'為0（或者x為0并且x'為1），特別地當k=-1時表示x=x'，……
意味著比k高的位與x相同，比k低的位沒有小于（大于）等于x的限制。
7.3.3.盧卡斯拆位數位dp
適用條件：求解對于0≤i≤n,0≤j≤min(i,m)中\((\sum C_i^j) \mod p\)或有多少對(i,j)滿足\(C_i^j\)是p的倍數，且p是一個小質數。
在模p的意義下，由盧卡斯定理得：\(C_n^m=C_{\lfloor n/p \rfloor}^{\lfloor m/p \rfloor}*C_{n \mod p}^{m \mod p}=C_{\lfloor \lfloor n/p \rfloor /p \rfloor}^{\lfloor \lfloor m/p \rfloor /p \rfloor}*C_{\lfloor n/p \rfloor \mod p}^{\lfloor m/p \rfloor \mod p}*C_{n \mod p}^{m \mod p}=\prod C_{n_{p_i}}^{m_{p_i}}\)。其中\(n_{p_i}\)表示n在p進制下的第i位。各個數位之間是相乘關系。
-
例1：給定n、m，求對于0≤i≤n,0≤j≤min(i,m)中有多少對(i,j)滿足\(C_i^j\)是p的倍數，且p是一個小質數
\(\Rightarrow\)在模p的意義下：\(C_i^j=\prod C_{i_{p_{i'}}}^{j_{p_{j'}}}=0\)。也就是求解有多少對(i,j)滿足在p進制下至少有一個數位j>i（注意仍要滿足原數j≤i！）。
int p;
int n[N],m[N],nidx,midx;
LL dp[N][2][2][2][2]; //dp[pos][ok][limit_n][limit_m][limit_nm]：第pos位、是否前面已經滿足某一數位的組合數為0（C_i^j中j>i）、是否有n對當前i的最高位可以填數的限定、是否有m對當前j的最高位可以填數的限定、是否有i對當前j的最高位可以填數的限定（要求原數j<=i）
LL dfs(int pos,bool ok,bool limit_n,bool limit_m,bool limit_nm)
{
if(pos==0) return ok;
if(dp[pos][ok][limit_n][limit_m][limit_nm]!=-1) return dp[pos][ok][limit_n][limit_m][limit_nm];
LL res=0;
int up_n=limit_n ? n[pos] : p-1,up_m=limit_m ? m[pos] : p-1;
for(int i=0;i<=up_n;i++)
for(int j=0;(!limit_nm || j<=i) && j<=up_m;j++)
res=(res+dfs(pos-1,ok || j>i/*滿足某一數位的組合數為0（C_i^j中j>i）*/,limit_n && i==up_n,limit_m && j==up_m,limit_nm && j==i))%MOD;
dp[pos][ok][limit_n][limit_m][limit_nm]=res;
return dp[pos][ok][limit_n][limit_m][limit_nm];
}
LL calc(LL nn,LL mm)
{
memset(dp,-1,sizeof dp);
//p進制
nidx=midx=0;
while(nn) n[++nidx]=nn%p,nn/=p;
while(mm) m[++midx]=mm%p,mm/=p;
//給較小的數的數位補零
for(int i=nidx+1;i<=midx;i++) n[i]=0;
for(int i=midx+1;i<=nidx;i++) m[i]=0;
return dfs(max(nidx,midx),false,true,true,true);
}
printf("%lld\n",calc(nn,mm));
-
例2：給定n、m，求\(\sum\limits_{i=1}^{+\infty} (C_{m}^{i}*C_{m}^{n-i}) \mod p\)，且p是一個小質數
因為i的上界就是n（i>n時，\(C_{m}^{n-i}=0\)），而式子又出現減法，當枚舉某一數位時\(n_{p_j}-i_{p_j}\)可能為負數，需要向高位借位，因此從低向高枚舉數位。記憶化搜索多傳一個變量borrow：當前的數位有沒有被上一個低數位借位。
int dfs(int pos,bool bor)
{
if(pos>max(nidx,midx)) return !bor; //最高位不能被借位
int &res=f[pos][bor];
if(res!=-1) return res;
res=0;
for(int i=0;i<p;i++)//i的上界就是n，若枚舉的i>n則一定會向最高位的高位借位而被上面特判掉。因此這里不用考慮當前數位可以填數的限定
{
int u1=i,u2=n[pos]-i-bor; //-bor：被低位借位
bool b=false;
if(u2<0) u2+=p,b=true; //若為負數，則向高位借位
res=(res+dfs(pos+1,b)*C(u1,m[pos])%p*C(u2,m[pos])%p)%p; //各個數位之間是相乘關系
}
return res;
}
int calc(int nn,int mm)
{
//得到nn和mm的數位數組，初始化f……
return dfs(1,0);
}
printf("%d\n",calc(nn,mm));
7.4.計數和計數類dp
- 不重不漏。
- 貢獻法：當原問題計數困難時，嘗試把角度轉化為每個元素對答案的貢獻。
- 一個集合的所有子集的元素種類數之和\(=\sum\limits_i(2^{cnt_i}-1)2^{n-cnt_i}\)。
- 序列min/max 計數嘗試排序后解決。
- 題目的信息中有的確定而有的不確定，不確定的個數就是方案數。
7.4.1.計數與貢獻
計數：\(f_i=\sum\limits_{\mathbb{C}_i} 1\)。
貢獻：\(g_i=\sum\limits_{\mathbb{C_i}} w(\mathbb{C_i})\)。
借助計數進行貢獻的狀態轉移：當從狀態j轉移到狀態i時，
- \(g_i=g_i*f_j*calc(i,j)+g_j*f_i*calc(i,j)\)。
- \(f_i=f_i*f_j*calc(i,j)\)。
7.4.2.集合計數和序列計數
定序序列計數=集合計數。
無序序列計數=定序序列計數*排列。
7.4.2.1.有序序列計數
有序：\(e.g.\)拓撲序……
通常設\(f[i][j]\)：i的排名是j的方案數/數值i位于前i個數的第j位。
確定形態的n個點的有根樹的拓撲序個數
1~n的全排列個數=n!。
只考慮“節點u必須排在以u為根的子樹中所有節點的前面”這一條件，只有n!/size[u]個排列是符合要求的。
每個節點的條件之間無關（條件只對當前節點有關）。
故\(ANS=\frac{n!}{\prod size[u]}\)。
7.4.3.區間貢獻區間
適用條件：給定若干個貢獻區間\([l_i,r_i]\)，詢問區間[L,R]在滿足\(L≤l_i≤r_i≤R\)時，一個貢獻區間\([l_i,r_i]\)會對其增加一個貢獻\(p_i\)（而不是\((r_i-l_i+1)*p_i\)）?？焖偾蟪鲈儐枀^間[L,R]的貢獻總和。
離線做法
-
將貢獻區間按左端點排序。
一個端點相同且貢獻相同的可以合并。下面以\([l_{i_1}\sim l_{i_2},r_i]\)為例子。（\([l_i,r_{i_1}\sim r_{i_2}]\)也是可以的。）
對于多個貢獻區間\([l_{i_1}\sim l_{i_2},r_i]\)，每一個都產生一個貢獻\(p_i\)：在掃描到\(r_i\)時，給序列區間\([l_{i_1},l_{i_2}]\)每個點上增加貢獻\(p_i\)。
也就是說掃描到一個單點時，要給其一個序列區間（不一定包含該單點）每個點上增加貢獻。
-
從左往右掃描單點。只有掃描到單點i時，才給單點i所對應的序列區間每個點上增加貢獻。（保證\(r_i≤R\)。包括上面區間合并成\([l_i,r_{i_1}\sim r_{i_2}]\)也是滿足的，因為在序列區間詢問到哪兒就是哪兒的貢獻。）
-
對于一個詢問區間[L,R]，在掃描完點L-1的時候，令答案-=此時序列區間[L,R]所有單點的貢獻和；在掃描完點R的時候，令答案+=此時序列區間[L,R]所有單點的貢獻和。（保證\(L≤l_i\)。）
上述操作可以借助線段樹實現。
7.4.4.匹配貢獻
在dp設計中，需要在一對匹配結束后才能確定該對匹配的貢獻。因此把貢獻放在匹配的第二個元素計算。
如果一對匹配是從2個序列中各選1個元素，則將2個序列的元素放在一起排序。
- 如果一對匹配的貢獻只與其中一個元素有關（\(e.g.\)min/max。），那么將元素排序，使得后面的元素與前面的元素匹配時，貢獻只與后面的元素有關，這樣dp就無后效性。
- 如果一對匹配的貢獻與兩個元素都有關，嘗試轉化角度，使得在后面的元素計算貢獻時只利用后面的元素的信息。
- \(\sum_j a_i*b_j→a_i*sumb_j\)。
- cnt（前i個元素中有……個）有時是一個好幫手。
- 直接計算→增量計算。
- 二分圖找環：右部節點負責新建交錯路，左部節點負責合并交錯路。
\(f[i][j]\)：前i個元素中已經選好了j對匹配的……。
狀態轉移：
- 當前元素與后面的元素匹配，該對匹配尚未結束，暫不計算貢獻：f[i][j]←f[i-1][j]。
- 當前元素與前面的元素匹配，在此時計算該對匹配的貢獻：f[i][j]←calc(f[i-1][j-1])。
7.4.5.樹上計數
7.4.5.1.樹上點對貢獻
在點對的lca處進行統計。
\(f_u\)：當前已合并到以u為根的子樹的節點的信息。
轉移：在遍歷到點u的一個兒子點v時，先把子樹v的信息\(f_v\)與\(f_u\)進行點對貢獻統計，再把\(f_v\)合并到\(f_u\)?？梢詤⒖?a target="_blank" rel="noopener nofollow">《圖論7.1.樹形dp求樹的直徑》。
- \(ANS←f_u\oplus f_v\)。
- \(f_u←f_v\)。
在dp中，(i,j)與(j,i)視為相同，不會重復計算。根據題意(i,j)與(j,i)是否算不同的貢獻，判斷最終答案是否要乘2。
可能還會配上啟發式合并。
7.4.5.2.樹上鏈貢獻與樹上鏈對貢獻
7.4.5.3.樹上連通塊計數
7.4.5.3.1.樹上連通塊計數
\(\sum\limits_{\mathbb{V}}1\)。
類似于《7.4.5.1.樹上點對貢獻》。
在連通塊中深度最小的點處進行統計。
下面簡記“連通塊中深度最小的點是點u的連通塊”為“以點u為根的連通塊”。
\(f_u\)：當前已統計的以點u為根的連通塊的個數。
轉移：在遍歷到點u的一個兒子點v時，情況分為刪除邊(u,v)和不刪除邊(u,v)，\(f_u=f_u*1+f_u*f_v\)。
邊界：\(f_u=1\)。其他為0。
\(ANS=\sum\limits_uf_u\)。
補充：另一種dp設計：\(f_{u,d}\)：考慮了以u為根的子樹，當前u所在連通塊的根的深度為d，……。
7.4.5.3.2.樹上連通塊貢獻
\(\sum\limits_{\mathbb{V}}w(\mathbb{V})\)。
所有連通塊大小的乘積=在每個連通塊內恰好選一個點的方案數。dp多開一維0/1表示當前連通塊有/無選關鍵點。
7.4.5.3.3.樹上連通塊內點貢獻
結合《7.4.1.計數與貢獻》和《7.4.5.3.2.樹上連通塊貢獻》。
\(\sum\limits_{\mathbb{V}}\sum\limits_{u\in\mathbb{V}}a_u\)。
\(f_u\)：當前已統計的以點u為根的連通塊的個數。
\(g_u\)：當前已統計的以點u為根的連通塊內的點的貢獻。
轉移：在遍歷到點u的一個兒子點v時，情況分為刪除邊(u,v)和不刪除邊(u,v)，
- \(g_u=g_u*1+(g_u*f_v+g_v*f_u)\)。
- \(f_u=f_u*1+f_u*f_v\)。
邊界：\(f_u=1,g_u=a_u\)。其他為0。
\(ANS=\sum\limits_ug_u\)。
7.4.5.3.4.樹上連通塊內點對貢獻
\(\sum\limits_{\mathbb{V}}\sum\limits_{u,v\in\mathbb{V}}(a_u\oplus a_v)\)，其中⊕滿足對加法的分配律。
異或：拆位，轉化為1的個數與0的個數的乘積，即可滿足對加法的分配律。
結合《7.4.5.1.樹上點對貢獻》和《7.4.5.3.3.樹上連通塊內點貢獻》。點對仍在點對的lca處進行統計，借助樹上連通塊的轉移將點對貢獻到其所屬的所有連通塊。
\(f_u\)：當前已統計的以點u為根的連通塊的個數。
\(g_u\)：當前已統計的以點u為根的連通塊內的點的貢獻。
\(h_u\)：當前已統計的以點u為根的連通塊內的點對的貢獻。
轉移：在遍歷到點u的一個兒子點v時，情況分為刪除邊(u,v)和不刪除邊(u,v)，
-
\(h_u=h_u*1+(h_u*f_v+h_v*f_u+g_u\oplus g_v)\)。
當不刪除邊(u,v)時，統計到含點u和點v的連通塊，情況分為點對都在當前以點u為根的連通塊（\(h_u*f_v\)）、點對都在以點v為根的連通塊（\(h_v*f_u\)）和點對分別在當前以點u為根的連通塊和以點v為根的連通塊（\(g_u\oplus g_v\)）。
-
\(g_u=g_u*1+(g_u*f_v+g_v*f_u)\)。
-
\(f_u=f_u*1+f_u*f_v\)。
邊界：\(f_u=1,g_u=a_u,h_u=0\)。其他為0。
\(ANS=\sum\limits_uh_u\)。
在dp中，(i,j)與(j,i)視為相同，不會重復計算。根據題意(i,j)與(j,i)是否算不同的貢獻，判斷最終答案是否要乘2。
7.4.5.3.5.樹上連通塊內點對貢獻和合并子樹信息模型
\(\sum\limits_{cnt_\mathbb{V}(\mathbb{G})=m+1}\sum\limits_{\mathbb{V}\in\mathbb{G}}\sum\limits_{u,v\in\mathbb{V}}(a_u\oplus a_v)\)，其中⊕滿足對加法的分配律。
\(f_{u,j}\)：在以點u為根的子樹內，當前已刪除了j條邊，已統計的以點u為根的連通塊的個數。
\(g_{u,j}\)：在以點u為根的子樹內，當前已刪除了j條邊，已統計的以點u為根的連通塊內的點的貢獻。
\(h_{u,j}\)：在以點u為根的子樹內，當前已刪除了j條邊，已統計的所有連通塊內的點對的貢獻。
\(bf_j,bg_j,bh_j\)：\(f_{u,j},g_{u,j},h_{u,j}\)的備份數組。備份后\(f_{u,j},g_{u,j},h_{u,j}\)清零。
轉移：在遍歷到點u的一個兒子點v時，
- 刪除邊(u,v)，
- \(h_{u,j+k+1}←bh_j*f_{v,k}+h_{v,k}*bf_j\)。
- \(g_{u,j+k+1}←bg_j*f_{v,k}\)。
- \(f_{u,j+k+1}←bf_j*f_{v,k}\)。
- 不刪除邊(u,v)，
- $h_{u,j+k}←bh_jf_{v,k}+h_{v,k}bf_j+bg_j\oplus g_{v,k} $。
- \(g_{u,j+k}←bg_j*f_{v,k}+g_{v,k}*bf_j\)。
- \(f_{u,j+k}←bf_j*f_{v,k}\)。
邊界：\(f_{u,0}=1,g_{u,0}=a_u,h_{u,0}=0\)。其他為0。
\(ANS=h_{1,m}\)。
在dp中，(i,j)與(j,i)視為相同，不會重復計算。根據題意(i,j)與(j,i)是否算不同的貢獻，判斷最終答案是否要乘2。
7.5.隨機化dp
適用條件：當滿足“x≤y”時可做→復雜度較低，可以dp多次。且題目要求最值。
x是“n/m/k”中的一個，y是比原范圍?。ê芏啵┑姆秶?.題中的另一個范圍；2.轉化題意（\(e.g.\)二分圖：范圍是2；在長度為n的序列中選出長度≥n/2的子序列：子序列中相鄰元素在原序列的下標的距離至多是2）。
-
直接把范圍限下來（e.g.將x隨機映射到大小為y的集合，集合內元素視為同種元素，每個集合內只能選一個元素），將某些不確定的因素確定下來，發現會很容易解決這個問題。
注意必須保證隨機化后得到的答案合法！
-
在草稿紙上計算：dp次數=限定時間內運算次數/1次dp的復雜度。再計算概率=(映射的正確數量（答案恰好映射到不同的集合）/映射的總數量)^dp次數。
-
按照限定后的范圍來dp。根據上面的計算來確定dp次數。在保證不超時的情況下，dp次數越多，正確率越高。答案對每次dp得到的值取最值。
int rand_cnt;
srand(time(NULL));
rand_cnt=; //dp次數=限定時間內運算次數/1次dp的復雜度
while(rand_cnt--)
{
get_rand(); //直接把范圍限下來，將x隨機映射到大小為y的集合，集合內元素視為同種元素，每個集合內只能選一個元素
ans=min/max(ans,dp()); //按照限定后的范圍來dp，答案對每次dp得到的值取最值
}
printf("%d\n",ans);
7.6.拉格朗日插值優化dp
適用條件：1.dp的內層狀態涉及值域；2.或要對每個全局的限制都做一遍dp，而全局的限制的范圍是值域；3.可以證明dp是一個多項式（邊界是多項式，轉移只涉及四則運算），最終只要求一個狀態的值。
以\(f_{i,j}\)，其中j是值域為例：
把\(f_{i,j}\)看作\(f_i(j)\)，第i個關于j的多項式。設g(i)為\(f_i(j)\)的次數。只需對于每個\(j\in[1,g(n)+1]\)求出\(f_n(j)\)，就可以利用拉格朗日插值\(O(g(n))\)或\(O(g(n)^2)\)求出\(f_n(W)\)。
求g(i)
-
簡單的情況
-
以轉移方程是\(f_{i,j}=f_{i,j-1}+j*f_{i-1,j-1}\)，邊界是\(f_{0,j}=1\)為例
\(\Rightarrow f_i(j)-f_i(j-1)=j*f_{i-1}(j-1)\)。
設\(f_i(x)=\sum\limits_{k=0}^{g(i)}a_{i,k}x^k\)，\(\Rightarrow \sum\limits_{k=0}^{g(i)}a_{i,k}j^k-\sum\limits_{k=0}^{g(i)}a_{i,k}(j-1)^k=j*\sum\limits_{k=0}^{g(i-1)}a_{i-1,k}(j-1)^k\)。
令k=g(i)，可求出左邊是g(i)-1次；令k=g(i-1)，可求出右邊是g(i-1)+1次。
\(\Rightarrow g(i)-1=g(i-1)+1\)，又因為g(0)=0（邊界），所以g(i)=2*i。
-
-
復雜的情況
\(f_i(j)\)的具體多項式是隨j一段一段確定的：對于每一段單獨求解分別拉插。
8.dp轉移優化
若候選集合擴大對答案無影響，則可考慮將候選集合擴大到其的內容與循環變量無關，有時可以起到優化的作用。
優化dp決策的候選集合。
8.1.剪枝有效狀態數
適用條件：發現有效狀態數很少。
- 注意題目特殊條件，有時轉移只需要從前x個狀態轉移而來。
- 若狀態之間兩兩不同不需要合并，則用vector存該輪的有效狀態，用該vector轉移到下一輪。
-
對于\(f_i=\max\limits_{j=0}^{i-1}/\min\limits_{j=0}^{i-1}(f_j+val(j,i))\)，對于每個i，最多有\(O(M)\)種不同的\(f_j\)或者\(val(j,i)\)：
維護決策點j的最小集合（具有相同的\(f_j\)或者\(val(j,i)\)的j合并為一個決策點），從該集合里轉移。復雜度為\(O(NM)\)。
-
- 若需要合并相同狀態，則用map（或vector+sort）/unordered_map存該輪的有效狀態，用該map/unordered_map轉移到下一輪。
8.2.矩陣乘法優化dp
適用條件：
- 可以抽象為一個長度為n的一維向量，該向量在每個單位時間發生一次變化；
- 變化的形式是一個線性遞推（只有若干個“加法”和“數乘”運算）；
- 遞推式每個時間可能作用于不同的數據上，但本身保持不變；
- 遞推的輪數很大，但向量長度n不大。
《數學2.1.2.3.應用：加速遞推》
8.3.數據結構優化dp
維護dp決策的候選集合。
一般作用是快速插入元素、刪除元素、查詢最值。把樸素在取值范圍中枚舉決策的時間優化為維護數據結構的時間。
8.3.1.前綴和優化
適用條件：內層循環是連續的，且可以前綴和。從而省略內層循環。
有時可以像推式子那樣調整枚舉順序，把連續的好求的變量放入內層循環，從而可以前綴和優化。
8.3.2.優化決策的候選集合
-
決策的候選集合的上界只增大，下界不變——一般一個變量維護最值。
-
決策的候選集合的上、下界均單調變化，每個決策在候選集合插入或刪除最多一次——單調隊列優化dp
基本條件：
f[i]=min/max{f[j]+val(i,j)} //L(i)<=j<=R(i)其中多項式val(i,j)中的每一項都只與i（如果是i-1，可直接把外層循環i看作定值）和j的其中一個有關。多維dp在執行內部循環時，把外部循環變量看作定值。單調隊列維護決策候選集合。
轉移的復雜度均攤 \(O(1)\) 。
![]()
“長度固定的最值”、“連續的”、“不能選擇超過m個連續的”……：單調隊列優化dp。
“已知最值，求固定長度”：二分長度，
check()函數中執行單調隊列優化dp。“最優性”、“隊頭狀態轉移”、“可行性+插入i”的順序要根據題意而定：是誰影響誰（\(e.g.\)滑動窗口：“可行性+插入i”對答案有影響，因此“可行性+插入i”要在“計算答案”的前面；單調隊列優化dp：計算答案時不能算上i本身，因此“可行性+插入i”要在“計算答案”的后面）。
int hh=0,tt=-1;
//q[++tt]=0;//插入f[0]=0，根據題意判斷f[0]是否合法、是否可以用于狀態轉移
//f[1]=...;q[++tt]=1;//若f[0]不合法，則先算出f[1]，再把f[1]插入隊列
for (int i=1;i<=n;i++)
{
if(q[hh]<L(i)) hh++ ;//可行性，當隊頭不在i的決策范圍內
f[i]=f[q[hh]]+val(i,q[hh]);//狀態轉移
while(hh<=tt && f[q[tt]]>=f[i]) tt--;//最優性
q[++tt]=i;//插入下一個i+1的候選集合
}
-
決策的候選集合的變化更復雜
多維dp在執行內部循環時，把外部循環變量看作定值。狀態轉移取最優決策時，簡單的限制條件用循環順序處理，復雜的用數據結構維護。
-
例題1：求多個區間覆蓋區間\([l,r]\)的最小花費
設n個按右端點排序的區間\([l_i,r_i]\)。
\(f[r_i]=\min\limits_{l_i-1≤x<r_i} \{ f[x] \}+c_i\)
本質上是一個帶有修改的區間最值操作。
線段樹維護。
技巧：按照右端點遞增排序。
-
例題2：求序列\(A\)長度為\(M\)的嚴格遞增子序列
求序列\(A\)長度為\(M\)的嚴格遞增子序列。
\(f[i][j]\)：前\(j\)個數以\(A_j\)結尾的數列，長度為\(i\)的嚴格遞增子序列有多少個（\(i\)、\(j\)均可作階段）。
特殊地，令\(A_0=-INF\)。
狀態轉移方程
-
const int INF=1<<30,MOD=1e9+7;
memset(f,0,sizeof f);
a[0]=-INF;
f[0][0]=1;
for(int i=1;i<=m;i++)
for(int j=1;j<=n;j++)
for(int k=0;k<j;k++)
if(a[k]<a[j]) f[i][j]=(f[i][j]+f[i-1][k])%MOD;
int ans=0;
for(int i=1;i<=n;i++) ans=(ans+f[m][i])%MOD;
#### 數據結構優化
樹狀數組維護前綴和。
在序列A（不包括$A_0$）中的數值的值域上建立樹狀數組。
把外層循環i看作定值。當j增加1時，k的取值范圍從0≤k<j變為0≤k<j+1，也就是多了一個k=j新決策。
設一個決策$(A_k,f[i-1,k])$。
1. 插入一個新決策。在j增加1前，把$(A_j,f[i-1,j])$插入集合：把$A_k$上的位置的值增加$f[i-1,k]$。
2. 給定一個值$A_j$，查詢滿足$A_k<A_j$的二元組對應的$f[i-1,j]$的和：在樹狀數組計算$[1,A_j-1]$的前綴和。
//樹狀數組維護前綴和
#include<bits/stdc++.h>
using namespace std;
const int N=1005,MOD=1e9+7;
int t,n,m,ans;
int a[N],f[N][N]; //f[i][j]：前i個數以Aj結尾的數列，長度為j的嚴格遞增子序列有多少個（i、j均可作階段）
int nums[N],cnt; //離散化
int tr[N]; //樹狀數組維護前綴和
inline int lowbit(int x){
return x&-x;
}
void add(int x,int v){
while(x<=cnt){
tr[x]=(tr[x]+v)%MOD;
x+=lowbit(x);
}
return ;
}
int sum(int x){
int res=0;
while(x>0){
res=(res+tr[x])%MOD;
x-=lowbit(x);
}
return res;
}
int main(){
scanf("%d",&t);
for(int C=1;C<=t;C++){
ans=0;
scanf("%d%d",&n,&m);
cnt=0;
for(int i=1;i<=n;i++){
scanf("%d",&a[i]);
nums[++cnt]=a[i];
}
//離散化
sort(nums+1,nums+cnt+1);
cnt=unique(nums+1,nums+cnt+1)-nums-1; //注意這里要-1
for(int i=1;i<=n;i++) a[i]=lower_bound(nums+1,nums+cnt+1,a[i])-nums+1;
for(int i=1;i<=n;i++) f[i][1]=1;
for(int j=2;j<=m;j++){
for(int i=1;i<=cnt;i++) tr[i]=0;
for(int i=1;i<=n;i++){
f[i][j]=sum(a[i]-1);
add(a[i],f[i][j-1]);
}
}
for(int i=1;i<=n;i++) ans=(ans+f[i][m])%MOD;
printf("Case #%d: %d\n",C,ans);
}
return 0;
}
例題3：用$\min\limits_{j<i,a[j]<a[i]}f_j$轉移狀態：相當于是二維偏序（j<i的要求已經在從小到大枚舉i時自然滿足）問題，使用以a[i]為下標的權值線段樹。
8.3.3.bitset優化\(O(\frac{F(N)}{\omega}),\omega=64\)
下面以狀態是\(f_{i,j}\)為例。
適用條件：1.\(f_{i,j}\)是布爾類型；2.轉移形如\(f_{i,j}←f_{i-1,j+c}\)，以便bitset輕松移位轉移。3.數據檔之間只相差幾倍常數。
新建bitset<N> f[N]，\(f_{i,j}\)的最內層維度j壓入bitset。由于\(f_{i,j}\)是布爾類型，所以轉移可以借助二進制運算，考慮轉移方程中\(f_{i,j}←f_{i-1,j+c}\)的c來確定二進制運算和移位問題。
8.4.斜率優化dp
基本條件：f[i]=min/max{f[j]+val(i,j)} //0<=j<i其中多項式val(i,j)包含一個同時與i（而不是i-1。如果是i-1，可把外層循環i看作定值）和j都有關的部分（如乘積項）。
技巧
-
注意包含i或j的高次項是可能用單調隊列或斜率優化的。
\(e.g.\)\(f[i]=\min\limits_{j=0}^{i-1} \{ f[j]+(s[i]-s[j])^2 \}→f[j]+s[j]^2=2*s[i]*s[j]+f[i]-s[j]^2\)
-
分類討論可以消滅成一個方程。
\(e.g.\)\(f[i]=\begin{cases} \min\{f[j]+val(i,j)\} & j\%2==0 \\ \min\{f[j]+val(i,j)+c\} & j\%2==1 \end{cases}\)
預處理\(g[i]=c*[j\%2==1]\)。則\(f[i]=\min\{ f[j]+val(i,j)+g[j] \}\)，然后就可以斜率優化了。
分析斜率
下面以最值min為例：
只有f[i]、j是未知量，其余（如a[i]）是已知量。
把min去掉，把關于j的值\(f[j]\pm a[j]\pm \cdots\)（視為y，僅與j有關的所有項）和a[i]a[j]（或a[i]b[j]或i*a[j]……。其中a[i]視為斜率k、a[j]視為x，i和j的乘積項）看作變量，要求的f[i]看作參數，其余看作常數：\(f[j]\pm a[j]\pm \cdots\)\(=\)\(a[i]\)\(*\)\(a[j]\)$\pm $$f[i]$$\pm \cdots$。
f[i]最小 → 即找到一個點\((a[j],f[j]\pm a[j]\pm \cdots)\)，使斜率為a[i]的直線過這個點的截距\(f[i]\pm \cdots\)最小 → 凸包問題。
取縱坐標函數get_y(int i){return f[i]+a[i]+...;}
求當前斜率（hh+1和hh、tt和tt-1、mid+1和mid兩點構成的斜率）是否小于要求斜率a[i]：(get_y(q[hh+1])-get_y(q[hh]))/(a[q[hh+1]]-a[q[hh]])<=a[i]。為了防止誤差（整除）還可以把分母乘過去。
8.4.1.斜率\(a[i]\)單調遞增，所加的點的橫坐標\(a[j]\)也單調遞增 \(O(N)\)
用單調的隊列（并非單調隊列）維護下凸包，且在滿足可行性后隊頭一定是答案。
由于所加的點的橫坐標單調遞增，所以可以用(get_y(q[tt])-get_y(q[tt-1]))*(a[i]-a[q[tt]])>=(get_y(i)-get_y(q[tt]))*(a[q[tt]]-a[q[tt-1]])判斷點是否在凸包上。
-
在查詢時，可以將隊頭小于當前斜率的點全部刪掉；
由于斜率單調遞增，所以可以用隊頭算出f[i]；（由于插入的判斷式包含f[i]，故要先用q[hh]算出f[i]）
-
在插入時，將隊尾所有不在凸包上的點全部刪掉；
插入i。（由于所加的點的橫坐標單調遞增，所以i一定滿足插入的條件）
int get_y(int i)
{
return f[i]+a[i]+...;
}
int hh=0,tt=-1;
//q[++tt]=0;//插入f[0]=0，根據題意判斷f[0]是否合法、是否可以用于狀態轉移
//f[1]=...;q[++tt]=1;//若f[0]不合法，則先算出f[1]，再把f[1]插入隊列
for(int i=1;i<=n;i++){
//注意hh<tt不取等號，因為要保證至少兩個元素
//隊頭元素斜率小于當前斜率就會被刪除，為了防止誤差（整除）把分母乘過去
while(hh<tt && get_y(q[hh+1])-get_y(q[hh])<=a[i]*(a[q[hh+1]]-a[q[hh]])) hh++;
//由于插入的判斷式包含f[i]，故要先用q[hh]算出f[i]
int j=q[hh];
f[i]=f[j]+val(i,j);
//當隊尾元素和它的前一個元素連成的直線的斜率大于i與它前一個連成的斜率就說明不是凸包下邊界，刪除隊尾
while(hh<tt && (get_y(q[tt])-get_y(q[tt-1]))*(a[i]-a[q[tt]])>=(get_y(i)-get_y(q[tt]))*(a[q[tt]]-a[q[tt-1]])) tt--;
q[++tt]=i;//插入i
}
printf("%lld\n",f[n]);
8.4.2.斜率不具有單調性，但是所加的點的橫坐標仍單調遞增 \(O(NlogN)\)
用單調的隊列（并非單調隊列）維護下凸包：
由于所加的點的橫坐標單調遞增，所以可以用(get_y(q[tt])-get_y(q[tt-1]))*(a[i]-a[q[tt]])>=(get_y(i)-get_y(q[tt]))*(a[q[tt]]-a[q[tt-1]])判斷點是否在凸包上。
-
在查詢時，只能二分查找并算出f[i]；（由于插入的判斷式包含f[i]，故要先用q[hh]算出f[i]）
-
在插入時，將隊尾所有不在凸包上的點全部刪掉；
插入i。（由于所加的點的橫坐標單調遞增，所以i一定滿足插入的條件）
int search(int k,int l,int r){
while(l<r){
int mid=(l+r)>>1;
if(get_y(q[mid+1])-get_y(q[mid])<=k*(a[q[mid+1]]-a[q[mid]])) l=mid+1;
else r=mid;
}
return q[l];
}
int hh=0,tt=-1;
//q[++tt]=0;//插入f[0]=0，根據題意判斷f[0]是否合法、是否可以用于狀態轉移
//f[1]=...;q[++tt]=1;//若f[0]不合法，則先算出f[1]，再把f[1]插入隊列
for(int i=1;i<=n;i++){
//注意hh<tt不取等號，因為要保證至少兩個元素
//由于插入的判斷式包含f[i]，故要先二分查找并算出f[i]
int j=search(a[i],hh,tt);
f[i]=f[j]+val(i,j);
//當隊尾元素和它的前一個元素連成的直線的斜率大于i與它前一個連成的斜率就說明不是凸包下邊界，刪除隊尾
while(hh<tt && (get_y(q[tt])-get_y(q[tt-1]))*(a[i]-a[q[tt]])>=(get_y(i)-get_y(q[tt]))*(a[q[tt]]-a[q[tt-1]])) tt--;
q[++tt]=i;//插入i
}
printf("%lld\n",f[n]);
8.4.3.任意情況
《數據結構?數8.7.3.1.李超線段樹優化斜率優化dp\(O(N \log N)\)》
8.5.決策單調性優化dp
8.5.1.四邊形不等式優化dp
基本條件：多項式val(i,j)（注意是小的數在前）包含i與j的高次乘積項，無法用單調隊列或斜率優化。但是val(i,j)是一個二元函數，可以考慮判斷其是否滿足四邊形不等式。
判定條件
設\(w(x,y)\)是定義在整數集合上的二元函數，若對于定義域上的任意整數\(a <= b <= c <= d\)，都有\(w(a,d) + w(b,c) >= w(a,c) + w(b,d)\)，則函數\(w\)滿足四邊形不等式。
或
設\(w(x,y)\)是定義在整數集合上的二元函數，若對于定義域上的任意整數\(a < b\)，都有\(w(a,b+1) + w(a+1,b) >= w(a,b) + w(a+1,b+1)\)，則函數\(w\)滿足四邊形不等式。
8.5.1.1.一維四邊形不等式
基本條件：****f[i]=min{f[j]+val(j,i)}+c //L(i)<=j<i其中多項式val(j,i)滿足四邊形不等式，L(i)是常數或關于i的單調遞增的一次函數。
具有決策單調性的判定（四邊形不等式優化dp的前提）
在狀態轉移方程\(f[i]=min\{f[j]+val(j,i)\}+c,L(i)<=j<i\)中，若\(val\)滿足四邊形不等式，則\(f\)具有決策單調性。
證明\(val\)滿足四邊形不等式：討論函數的增減性、求導、打表觀察val。
決策單調性的定義
對于形如\(f[i]=min\{f[j]+val(j,i)\}+c,L(i)<=j<i\)的狀態轉移方程，記\(p[i]\)為令\(f[i]\)取到最小值的\(j\)的值，即\(p[i]\)是\(f[i]\)的最優決策。若\(p\)在\([1,N]\)上非嚴格單調遞增，則稱\(f\)具有決策單調性。
當f有決策單調性時的優化做法： \(O(N^2)\)優化到\(O(NlogN)\)
8.5.1.1.1.單調的隊列寫法
優點：可以在線。
利用決策單調性和一個單調的隊列維護決策（三元組(i,l,r）：決策i在f[l~r]上比其他任何決策都更優）集合。
根據L(i)求出R(j)：狀態j能合法轉移到的最大的狀態。
注意，只要問題的決策具有單調性，無論問題是不是dp，都可套用下面insert()函數。
void insert(int i)
{
int pos=q[tt].r+1;
//不斷取出隊尾(j,l,r)
//若對于f[l]來說，i是比j更優的決策，則直接刪除隊尾，記pos=l
while(hh<=tt && f[i]+val(i,q[tt].l)+c<=f[q[tt].j]+val(q[tt].j,q[tt].l)+c)
{
pos=q[tt].l;
tt--;
}
//若對于f[r]來說，i是比j更優的決策，則二分查找求出pos：在pos之前，決策j更優；在pos及pos之后，決策i更優
if(hh<=tt && f[i]+val(i,q[tt].r)+c<=f[q[tt].j]+val(q[tt].j,q[tt].r)+c)
{
int l=q[tt].l,r=q[tt].r;
while(l<r)
{
int mid=(l+r)>>1;
if(f[i]+val(i,mid)+c<=f[q[tt].j]+val(q[tt].j,mid)+c) r=mid;
else l=mid+1;
}
q[tt].r=r-1;
pos=r;
}
//把新的(i,pos,N)插入隊尾
if(pos<=R(i)) q[++tt]={i,pos,R(i)};
return ;
}
hh=0,tt=-1;
/*
q[++tt]={0,1,R(0)};//插入f[0]=0，根據題意判斷f[0]是否合法、是否可以用于狀態轉移
f[1]=...;q[++tt]={1,1,R(1)};//若f[0]不合法，則先算出f[1]，再把f[1]插入隊列
*/
for(int i=1/*若上面把f[1]插入隊列，則這里i是從2開始*/;i<=n;i++)
{
//可行性，檢查隊頭
if(q[hh].r<i) hh++;//不滿足要求刪除隊頭
q[hh].l=i;//滿足要求令l=i
//利用隊頭計算出f[i]
f[i]=f[q[hh].j]+val(q[hh].j,i)+c;
//插入新決策i
insert(i);
}
8.5.1.1.2.離線分治寫法
優點：好寫。當val(j,i)必須用類似莫隊的方式求解時，仍然可以保證復雜度。缺點：必須離線。
對于每一層[l,r]都先在決策區間\([d_l,d_r]\)枚舉決策點暴力計算\(f_{mid}\)并記錄\(f_{mid}\)的最優決策點\(d_{mid}\)，遞歸計算[l,mid-1]/[mid+1,r]時，他們的決策區間縮小為\([d_l,d_{mid}]/[d_{mid},d_r]\)，下一層決策點的枚舉量減半，因此總的時間復雜度是\(O(N\log N)\)。
當val(j,i)必須用類似莫隊的方式求解時，每一層指針移動的距離是\(O(N)\)的，分治一共有\(O(\log N)\)層，因此分治過程中計算val(j,i)的復雜度仍然可以保證。
int n;
int a[N];
LL res,L,R,cnt[N];
LL f[N];
//當val(j,i)必須用類似莫隊的方式求解時
LL val(int l,int r)
{
while(l<L) L--,add(a[L]);
while(R<r) R++,add(a[R]);
while(L<l) del(a[L]),L++;
while(r<R) del(a[R]),R--;
return res;
}
void divide(int l,int r,int dl,int dr) //l、r：求解區間；dl、dr：決策區間
{
if(l>r/*超過邊界*/ || dl>dr/*沒有合法的轉移，只能無解*/) return ;
int mid=(l+r)>>1,dmid; //dmid：f[mid]的最優決策
for(int i=dl;i<=dr;i++)
if(f[mid]>f[i]+val(i,mid))
{
f[mid]=f[i]+val(i,mid);
dmid=i;
}
divide(l,mid-1,dl,dmid);
divide(mid+1,r,dmid,dr);
return ;
}
scanf("%d",&n);
for(int i=1;i<=n;i++) scanf("%d",&a[i]);
L=1,R=n;
for(int i=1;i<=n;i++) add(a[i]);
memset(f,0x3f,sizeof f);
f[0]=0;
divide(1,n,0,n-1);
printf("%lld\n",f[n]);
8.5.1.2.二維四邊形不等式
基本條件：f[i][j]=min{f[i][k]+f[k+1][j]+val(j,i)} //i<=k<j或f[i][j]=min{f[i][k]+f[k][j]+val(j,i)} //i<=k<=j。
具有決策單調性的判定（四邊形不等式優化dp的前提）
在狀態轉移方程\(f[i][j]=\min\limits_{i\le k<j}\{f[i][k]+f[k+1][j]+val(i,j)\}\)或\(f[i][j]=\min\limits_{i\le k\le j}\{f[i][k]+f[k][j]+val(i,j)\}\)中，若：
- \(val\)是二元組函數，且滿足四邊形不等式；
- 對于任意的\(a <= b <= c <= d\)，有\(val(a,d) >= val(b,c)\);
- \(f[i][i]=val(i,i)=0\)。
則\(f\)也滿足四邊形不等式。
決策單調性的定義
在狀態轉移方程\(f[i][j]=\min\limits_{i\le k<j}\{f[i][k]+f[k+1][j]+val(i,j)\}\)或\(f[i][j]=\min\limits_{i\le k\le j}\{f[i][k]+f[k][j]+val(i,j)\}\) 中（特別地，\(f[i][i]=val(i,i)=0\)），記\(p[i][j]\)為令\(f[i][j]\)取到最小值的\(k\)的值。如果\(f\)滿足四邊形不等式，那么對于任意\(i < j\)，有\(p[i][j-1] <= p[i][j] <= p[i+1][j]\)。
由此可以縮小決策候選集合p。
由于要用到p[i][j-1]、p[i+1][j]，所以倒序i，正序j。
8.5.1.2.1. 應用——石子合并
石子合并
只能合并相鄰的石子堆
合并果子（參見《數據結構?數4.2.\(Huffman\)樹》）
任意兩堆果子均可合并
8.5.1.2.1.1.區間石子合并
參見《動態規劃2.5.1.區間dp——區間石子合并》。
8.5.1.2.1.2.環形石子合并
參見《動態規劃5.1.破環成鏈轉化為線性dp》。
8.5.1.2.1.3.二維四邊形不等式優化區間石子合并 \(O(N^3)\)優化到\(O(N^2)\)
-
二維四邊形不等式優化區間石子合并
dp \(O(N^3)\)
狀態轉移方程
for(int i=n-1;i>=1;i--)
for(int j=i+1;j<=n;j++)
for(int k=i;k<j;k++)
f[i][j]=min(f[i][j],f[i][k]+f[k+1][j]+(sum[j]-sum[i-1]));
二維四邊形優化 \(O(N^2)\)
sum[j]-sum[i-1]是區間和，滿足四邊形不等式\(w(i,j)\)：取到等號。
根據上述兩條定理，只需要在\(p[l][r-1] <= k <= p[l-1][r]\)的范圍內對\(k\)進行枚舉，求出\(f[l][r]\)和\(p[l][r]\)。
#include<bits/stdc++.h>
using namespace std;
const int N=5005;
int n;
int sum[N],f[N][N],p[N][N];
int main(){
memset(f,0x3f,sizeof f);
scanf("%d",&n);
for(int i=1;i<=n;i++){
scanf("%d",&sum[i]);
sum[i]+=sum[i-1];
f[i][i]=0;
p[i][i]=i;
}
for(int i=n-1;i>=1;i--)
for(int j=i+1;j<=n;j++)
for(int k=p[i][j-1];k<=p[i+1][j];k++){
int t=f[i][k]+f[k+1][j]+sum[j]-sum[i-1];
if(f[i][j]>t){
f[i][j]=t;
p[i][j]=k;
}
}
printf("%d\n",f[1][n]);
return 0;
}
8.5.1.2.1.4.Garsia Wachs算法優化區間石子合并 \(O(N^3)\)優化到\(O(N\log N)\)
- Garsia Wachs算法優化區間石子合并
- 找到滿足\(a_{k-1} <= a_{k+1}\)的最小下標\(k\)；
- 找到滿足\(a_{j-1} > a_{k-1} + a_k\)且\(j<k\)的最大的\(j\)；
- 清除\(a_{k-1}\)和\(a_k\)；
- 在\(a_{j-1}\)后面插入\(a_{k-1}+a_k\)；
- \(a_{-1}\)和\(a_{n+1}\)可以定義為\(INF\)處理。
#include<bits/stdc++.h>
using namespace std;
const int N=5e4+5;
int n,ans,s_end;
int stone[N];
void merge(int x)
{
int sum=stone[x]+stone[x-1],k,s_end_now;
ans+=sum; //合并
for(k=x;k<s_end;k++) stone[k]=stone[k+1]; //清除stone[v]
for(k=x-1;stone[k-1]<sum && k>1;k--) stone[k]=stone[k-1]; //清除stone[x-1]并找到x-1前面第一個stone大于sum的下標k-1
stone[k]=sum; //在k-1后面插入k
//看能不能繼續合并
s_end_now=--s_end;
while(k>2 && stone[k-2]<=stone[k])
{
merge(k-1);
k-=s_end_now-s_end; //每遞歸調用merge一次，K會減少1，s_end_now-s_end就是調用次數
}
return ;
}
int main()
{
while(scanf("%d",&n),n)
{
ans=s_end=0;
for(int i=1;i<=n;i++)
{
int x;
scanf("%d",&x);
stone[++s_end]=x;
//邊輸入，邊進行可能的合并
while(s_end>2 && stone[s_end-2]<=stone[s_end]) merge(s_end-1);
}
//剩余的都是從后合并，因為定義stone[s_end+1]=INF
while(s_end>1) merge(s_end);
printf("%d\n",ans);
}
return 0;
}
8.5.2.雙指針優化
適用條件：答案隨著編號有單調性。
8.6.凸單調性優化dp
8.6.1.凸包
適用條件：求最值、和斜率有關（本質上就是對斜率二分）、可以把題目轉化為凸包形式、沒有i、j的乘積項。
精度開大！
若給定的點無序先排序！
8.6.1.1.凸包優化轉移
適用條件：形如\(f[i]/ans=\max\limits_{j=1}^{i-1} \frac{b_i-d_j}{a_i-c_j}\)。
可以把max內的部分轉化為\((a_i,b_i)\)和\((c_j,d_j)\)兩點連線的斜率。對于i時刻，\((a_i,b_i)\)是確定的，所以把\((c_j,d_j),1\le j\le i-1\)維護成一個凸包，在上面二分斜率。
根據題目性質（\(e.g.\)給定的點的橫坐標和縱坐標都單調遞增）以及在草稿紙上模擬，畫出整個凸包，根據是求斜率最大值還是最小值判斷維護上凸包還是下凸包。
插入當前點\((c_i,d_i)\)和二分斜率的順序？判斷當前查詢是否可以考慮當前點。
下面以“給定的點的橫坐標和縱坐標都單調遞增，求斜率最大值”為例：
在草稿紙上畫出整個凸包可知：維護下凸包。
- 若給定的點無序先排序，插入初始點。
- 枚舉每一個i：
- 可行性：用點\((c_i,d_i)\)維護下凸包。
- 判斷當前查詢是否可以考慮當前點來決定插入當前點\((c_i,d_i)\)和二分斜率的順序。
- 二分斜率后得到f[i]=max\((a_i,b_i)\)和\((c_j,d_j)\)兩點連線的斜率。
int top;
struct Slope
{
double x,y;
bool operator < (const Slope &qw) const
{
if(x==qw.x) return y>qw.y;
return x<qw.x;
}
Slope operator - (const Slope &qw) const
{
return {x-qw.x,y-qw.y};
}
}s[N]; //棧維護凸包
double slope(Slope a,Slope b) //求斜率
{
if(cmp(a.x,b.x)==0) return INF; //斜率無窮大
return (a.y-b.y)/(a.x-b.x);
}
double cross(Slope a,Slope b)
{
return a.x*b.y-a.y*b.x;
}
double area(Slope a,Slope b,Slope c)
{
return cross(b-a,c-a);
}
sort(poi+1,poi+n+1); //若給定的點無序先排序
s[0]={0,0}; //插入初始點
for(int i=1;i<=n;i++)
{
Slope p1={c[i],d[i]},p2={a[i],b[i]};
//可行性：用點(c[i],d[i])維護下凸包
while(top && sign(cross(s[top-1],s[top],p1))<=0) top--;
//判斷當前查詢是否可以考慮當前點來決定插入當前點i和二分斜率的順序
//插入當前點i
s[++top]=p1;
//最優性：二分斜率。斜率最大在下凸包的點
int l=1,r=top,res=0;
while(l<=r)
{
int mid=(l+r)>>1;
if(sign(slope(s[mid-1],p2),slope(s[mid],p2))<0) l=mid+1,res=mid;
else r=mid-1;
}
//二分斜率后得到f[i]=max(a[i],b[i])和(c[j],d[j])兩點連線的斜率
f[i]=slope(s[res],p2);
}
8.6.1.2.凸包優化狀態
適用條件：給定n個點\((x_i,y_i)\)，\(f_i(k)=calc(x_i,y_i,k)\)，求出一個k，使得\(\max\limits_{i=1}^n f_i(k)\)最小，并輸出最小值。
- 將\(f_i(k)\)轉化為斜率為\(k_i\)且過點\((x_i,y_i)\)的直線的某一個值（\(e.g.\)斜率、橫縱截距）。此時可推出對于當前的\(k_i\)，該直線與凸包上點i的\(f_i(k_i)\)≥\(f_j(k_i),1≤j≤n\)。
- 將問題轉化為：在凸包上找一點i，使得一個斜率為\(k_i\)的直線與凸包相切于點i的\(f_i(k_i)\)最?。ㄗ⒁庖獫M足前提：對于當前的\(k_i\)，該直線與凸包上點i的\(f_i(k_i)\)≥\(f_j(k_i),1≤j≤n\)）。
- 在草稿紙上通過計算求出\(h_i(k)\)：直線斜率為k且經過點i時的\(f_i(k)\)，顯然k是有取值范圍的：k必須在凸包上點i兩邊線段的斜率之間。
- 求出凸包。
- 枚舉凸包上每一個點i。在k的取值范圍內求出最小的\(h_i(k)\)更新答案ans。
8.6.2.slope tirck
適用條件：轉移代價函數滿足：1.連續；2.分段線性函數（斜率變化常是整數）；3.凸函數。
第i輪循環的圖像放在前i輪來看是一定正確的。
對于大部分的題目，形如下面的狀態設計。
8.6.2.1.slope tirck
狀態設計
對于大部分的題目，形如：\(f_{i,x}=\min\limits_{x-b_i\le x' \le x-a_i} \{f_{i-1,x'}\}+|x-c_i|\)。設\(f_{i,x}\)前i個且第i個是x（x的范圍是值域大小）的最值，把\(f_{i,x}\)看成平面上的函數圖像\(f_i(x)\)。且轉移涉及到\(|x-c_i|\)，看成關于x的絕對值函數。
大膽設計第二維為值域大小。
slope tirck狀態轉移
正確性證明：斜率相加、截距相加。
用兩個堆（維護拐點的橫坐標單調）來維護兩個有序可重集來描述滿足上面性質的函數?？芍丶拿總€元素表示函數的一個拐點的橫坐標，每種元素的個數表示函數在這個位置斜率變化了幾（下凸函數就是表示增加了幾）。一個大根堆維護斜率為0的段的左邊的函數，一個小根堆維護右邊。也就是說兩個堆的堆頂就是斜率為0的段的兩端。
-
當\(b=\infty,a=1\)時：\(f_{i,x}=\min\limits_{x'<x} \{f_{i-1,x'}\}+|x-c_i|\)：
顯然\(\min\limits_{x'<x}\{ f_{i-1,x'} \}\)是\(f_{i-1,x}\)的前綴最小值。所以在圖像上\(\min\limits_{x'<x}\{ f_{i-1,x'} \}\)左邊是凸包，右邊是水平的。所以我們可以只用一個左邊的堆（維護左邊和水平段）+一條右邊的直線（k和b）來維護圖像。
-
先考慮\(\min\limits_{x' < x}\{f_{i-1,x'}\}\)的轉移，把\(f_{i-1,x}\)的圖像變成\(f_{min}(x)=\min\limits_{x' < x}\{f_{i-1,x'}\}\)的圖像。
我們要把右邊的直線打平：不斷彈出左邊的堆的堆頂直到右邊的直線的斜率為0：每彈出一個堆頂我們可以利用目前的k和b得知其的縱坐標，然后我們更新k和b。
-
再考慮\(|x-c_i|\)的轉移，把\(f_{min}(x)\)的圖像變成\(f_{i,x}\)的圖像。
加入絕對值函數，分析可知在c處斜率的變化為2，所以向左邊的堆中放入兩個c，并更新k和b（截距相加，斜率相加）。
-
LL k,b;
priority_queue<LL> q;
//初始的函數是f=0\xRightarrow{+絕對值|x-c|}f_1
scanf("%lld",&c);
q.push(c),q.push(c);
k++,b-=c;
for(int i=2;i<=n;i++)
{
scanf("%lld",&c);
//f_{i-1,x}\xRightarrow{前綴最小值}f_{min}(x)
while(k)
{
LL x=q.top(),y=k*x+b;
q.pop();
k--;
b=y;
}
//f_{min}(x)\xRightarrow{+|x-c_i|}f_{i,x}
q.push(c),q.push(c);
k++,b-=c;
}
- \(f_{i,x}=\min\limits_{x-b_i\le x' \le x-a_i} \{f_{i-1,x'}\}+|x-c_i|\)：
-
先考慮\(\min\limits_{x-b_i\le x' \le x-a_i}\{f_{i-1,x'}\}\)的轉移，把\(f_{i-1,x}\)的圖像變成\(f_{min}(x)=\min\limits_{x-b_i\le x' \le x-a_i}\{f_{i-1,x'}\}\)的圖像。
對于下凸殼，在草稿紙上模擬可知：左邊的部分會向右平移\(a_i\)個單位，右邊的部分會向右平移\(b_i\)個單位。
下面以維護右邊的部分為例：也就是說，對于一個堆中的所有元素，都要加上一個相同的值\(b_i\)。因此這里用懶標記維護：tagr：右邊的點的現在實際坐標=堆中的元素+tagr。（注意tagr與斜率為0的段無關！?。。?/p>
-
再考慮\(|x-c_i|\)的轉移，把\(f_{min}(x)\)的圖像變成\(f_{i,x}\)的圖像。
顯然這個絕對值函數的分界點是\(x=c_i\)。分類討論：當\(c_i\)<左邊堆的堆頂，當\(c_i\)>右邊堆的堆頂，\(c_i\)在中間。
下面以\(c_i\)<左邊堆的堆頂為例：\(c_i\)的左邊斜率都減一，而右邊都加一，等于在$ c_i\(的位置減少了2，所以朝左邊的堆加入兩個\) c_i$，加入左邊的堆時記得減去懶標記tagl，因為點的現在實際坐標=堆中的元素+懶標記，
L.push(x[i]-tagl);L.push(x[i]-tagl);。同時斜率為0的段的兩端不再是之前兩個堆的堆頂，而是左邊的堆的堆頂和pop后的堆頂，所以要拿出左邊的堆的堆頂并加入右邊的堆中，從堆中拿出時記得加上懶標記tagl得到點的現在實際坐標，加入時同樣要注意減去懶標記tagr，LL l=L.top()+tagl;L.pop();R.push(l-tagr);。注意先pop()再push(c_i)。
-
int n;
LL c,a,b,ans;
priority_queue<LL> L; //一個大根堆維護斜率為0的段的左邊的函數
priority_queue<LL,vector<LL>,greater<LL> > R; //一個小根堆維護右邊
LL tagl,tagr; //點的現在實際坐標=堆中的元素+懶標記（注意懶標記與斜率為0的段無關?。。。?
scanf("%d",&n);
scanf("%lld",&c);
L.push(c),R.push(c); //初始的函數是f=0\xRightarrow{+絕對值|x-c|}f_1
for(int i=2;i<=n;i++)
{
scanf("%lld%lld%lld",&a,&b,&c);
//f_{i-1}\xRightarrow{轉移的范圍}f_min
tagl+=a,tagr+=b;
//f_min\xRightarrow{+絕對值函數|x-c|}f_i
//注意先pop()再push(c)
int l=L.top()+tagl,r=R.top()+tagr;//?。?！注意從堆中拿出時加上懶標記
if(c<l) //只關心斜率變化，平移在上面已經處理好了，不屬于加絕對值的部分
{
L.pop(),R.push(l-tagr);//！?。∽⒁夥湃肭耙葴p去懶標記
L.push(c-tagl),L.push(c-tagl);
}
else if(c>r)
{
R.pop(),L.push(r-tagl);
R.push(c-tagr),R.push(c-tagr);
}
else
{
L.push(c-tagl),R.push(c-tagr);
}
}
技巧
-
圖像的截取。
使用時間：題目對最終的方案有限制。
\(e.g.\)將一個序列x轉化為序列y，要求之一是\(y_i\in[1,q]\)。
此時凸包的圖像的定義域是不完整的。
對凸包圖像進行變換時是對之前已經不完整的凸包圖像進行變換！并且得到的新的圖像又要對[1,q]截取圖像。
\(e.g.\)定義域為[1,q]的圖像向右平移delta單位并截取后的圖像定義域為[1+delta,q]。
事實上不需要在堆中真的截取，只要在取出答案時在相應的定義域找最值即可。
-
圖像變換：斜率為0的一段的左邊向上平移，斜率為0的一段向右平移delta個單位，空缺處插入一段斜率為-1的線段。
把斜率為0的一段的左端點x彈出，再插入x+delta即可。
-
感性證明
\(e.g.\)
![]()
-
求最終答案
因為我們設計的方程\(f_{i,x}\)表示考慮前i個點的最值，所以最終的答案是最終圖像的最小函數值。
-
定義域沒有限制時，最終圖像的最小函數值是斜率為0的一段的函數值。
求斜率為0的一段的函數值：
- 方法一：求出f(0)。適用條件：能求出f(0)，且較難記錄截距。 求出f(0)。因為slope trick記錄了拐點所以知道了每一段的斜率。所以可以由f(0)知道每個拐點的函數值。 對于每一個拐點i，f0減去1~i*拐點前后的斜率之差。最終得到當前圖像的最小函數值。
while(L.size())
{
f0-=L.top();
L.pop();
}
printf("%d\n",f0);
- 方法二：記錄斜率為0的一段的截距。
適用條件：無法求出f(0)。
- 對于$f_{i,x}=\min\limits_{x'<x} \{f_{i-1,x'}\}+|x-c_i|$：本身就已經記錄了右邊的直線。最后輸出截距b即可。
- 對于$f_{i,x}=\min\limits_{x-r\le x' \le x-l} \{f_{i-1,x'}\}+|x-c_i|$：計算每次轉移斜率為0的一段的函數值的偏移量
$f_{i,x}$斜率為0的一段的函數值相對于$f_{i-1,x}$的**函數值增加量=c與斜率為0的一段的橫坐標距離**。
- 證明
這一段是由$f_{i-1,x}$的**斜率為-1**（c<左邊堆的堆頂）或**1**（c>右邊堆的堆頂）的一段+絕對值函數得到的。因此函數值的增加量=c與斜率為0的一段的橫坐標距離，而不是圖像的y。
if(c<l){ans+=l-c;}
else if(c>r){ans+=c-r;}
else{ans+=c-c;}
-
定義域有限制時（\(e.g.\)截?。?，最終圖像的最小函數值不一定是斜率為0的一段的函數值。
此時需要得到方案，答案=calc(方案,原值)。
得到方案見《動態規劃8.5.2.3.輸出方案》
8.6.2.2.樹上slope trick
形如\(f_{u,x}=\sum\limits_{v\in son(u)}\min\limits_{x-b_i\le x' \le x-a_i} \{f_{v,x'}\}+|x-c_i|\)。
- slope trick先求出\(f_{u,x}\)。
- 把\(f_{u,x}\)轉化為u為\(fa_u\)意義下的\(f'_{u,x}\)。
- 使用可并堆（正確性證明：斜率相加、截距相加）把\(f'_{u,x}\)合并到\(f_{fa_u,x}\)。
8.6.2.3.輸出方案
注意：第i輪循環的圖像放在前i輪來看是一定正確的（因為本身第i輪循環的圖像就是從前面順推過來的，歸納法證明。），放在全局來看是不一定正確的。
若\(y_n\)在最終凸包上，則一定能構造一組解。
-
若方案有自己的限制（\(e.g.\)\(y_i\in[1,q]\)）：在維護凸包時滿足限制（\(e.g.\)截取）。
-
若方案有互相的限制（\(e.g.\)\(y_{i+1}-y_i\in[a,b]\)）：
初步構造\(y_i\)為第i輪循環的圖像的最低點。然后從n-1開始倒推方案
y[i]=min(y[i],y[i+1]-a);y[i]=max(y[i],y[i+1]-b);。-
證明
可行性：第n輪循環的圖像放在前n輪看是一定正確的。所以倒推方案是一定存在一組解的。
最優性：倒推方案時，若\(y_{i+1}-b\le y_i \le y_{i+1}-a\)，即\(y_i\)能取到凸包最低點而且與后面不沖突的，根據貪心這是一定不劣的；若\(y_i<y_{i+1}-b\)，由于一定存在一組解，根據貪心此刻令\(y_i=y_{i+1}-b\)一定是最優的，因為初步構造時\(y_i\)時凸包的最低點，而此刻\(y_i\)離\(y_{i+1}-b\)最近，那么取這個端點一定最優；若\(y_{i+1}-a<y_i\)，同理。
Q：萬一只有\(y_n=q\)時才有解呢？
A：那么最終的圖像一定是一個點\((n,q)\)。
-
https://www.luogu.com.cn/blog/foreverlasting/solution-p4272
8.6.3.wqs二分
8.6.3.1.wqs二分\(O(N\log N)\)
適用條件： 求n 個物品恰好選 k 個的情況下的最值，函數圖像（橫坐標是選幾個物品，縱坐標是最值）具有凸性。
下面以求最小值為例：
-
難點。證明或打表發現函數圖像具有下凸性。決定當多種方案的最值相等時，選擇物品個數少的方案還是物品個數多的方案，以便二分。（下面以選擇物品個數少的方案為例）
-
二分mid（具體怎么二分見第4步），選一個物品要額外花費mid的代價。
-
求出n個物品選若干個的情況下的最值res（表示最值處的縱坐標）和選擇物品cnt（在“選擇物品個數少的方案”的情況下，表示最值處平臺的左端點橫坐標）的個數。當多種方案的最值相等時，選擇物品個數少的方案。
-
難點。在草稿紙上畫出圖像可知：
- 若cnt<k，應令選擇物品多的最值更小，圖像最低峰向右走，mid應更小，且由于“選擇物品個數少的方案”，此時的mid有可能會使得\(y_k=y_{cnt}=res\) 取到最值處（圖像意義：mid的圖像的最值處平臺的左端點橫坐標cnt<橫坐標k，此時k有可能在最值處平臺上）成為答案，所以
r=mid;。 - 若cnt>k，同理，與cnt<k的情況區別在于此時的mid不可能成為答案，所以
l=mid+1;。 - 若cnt==k，此時mid的圖像的最值處平臺的左端點橫坐標就是k，由于上文的分析
r=mid;取等，因此該情況直接規約為r=mid;。
由于上文的分析
r=mid;l=mid+1;，因此mid=(l+r)>>1;才可以使得二分正常進行。 - 若cnt<k，應令選擇物品多的最值更小，圖像最低峰向右走，mid應更小，且由于“選擇物品個數少的方案”，此時的mid有可能會使得\(y_k=y_{cnt}=res\) 取到最值處（圖像意義：mid的圖像的最值處平臺的左端點橫坐標cnt<橫坐標k，此時k有可能在最值處平臺上）成為答案，所以
-
二分結束后（l=r），k一定在l的圖像的最值處平臺。由于可能最后一次二分的mid≠l，所以此時應執行一次
check(l,res,cnt)。最終答案是res-l*k（注意不是res-l*cnt：res-l*cnt錯誤的原因：雖然cnt和k都在l的圖像的最值處平臺，但是原圖像cnt和k不一定在同一平臺上。res-l*k正確的原因：\(y_k=y_{cnt}=res\)。）。
void calc(int mid,int &res,int &cnt)
{
res=cnt=0;//不要忘記初始化
//求出n個物品選若干個的情況下的最值res和選擇物品cnt的個數
//當多種方案的最值相等時，選擇物品個數少的方案
//選一個物品要額外花費mid的代價
}
int l=-UP,r=UP;
while(l<r)
{
int mid=(l+r)>>1,res,cnt;
calc(mid,res,cnt);
if(cnt<=k) r=mid;
else l=mid+1;
}
check(l,res,cnt);
printf("%lld\n",res-l*k);
8.6.3.2.wqs二分套wqs二分\(O(N \log^2 N)\)
當要求兩種物品分別恰好選\(k_1\)個和\(k_2\)個的情況下的最值時，第一層二分mid1：每選第一種物品要額外花費mid1的代價；第二層二分mid2：每選第二種物品要額外花費mid2的代價；然后再check(mid1,mid2)：求出兩種物品分別選若干個的最值val、選第一種物品的個數cnt1以及選第二種物品的個數cnt2。其余的分析和wqs二分一樣。
int k1,k2;
int ans;
struct Wqs
{
int val,cnt1,cnt2;//val：兩種物品分別選若干個的最值；cnt1：選第一種物品的個數；cnt2：選第二種物品的個數
};
Wqs check(int mid1,int mid2){} //返回兩種物品分別選若干個的最值、選第一種物品的個數以及選第二種物品的個數
scanf("%d%d",&k1,&k2);
//此處二分寫法有問題，待修改
int l1=-UP,r1=UP;
while(l1<=r1)
{
int mid1=(l1+r1)>>1;
Wqs res1,res2;
int l2=-UP,r2=UP,mid2;
while(l2<=r2)
{
int mid=(l2+r2)>>1;
res2=check(mid1,mid);
if(res2.cnt2<=k2) r2=mid,res1=res2,mid2=mid;
else l2=mid;
}
if(res1.cnt1<=k1) r1=mid1,ans=res1.val-k1*mid1-k2*mid2;
else l1=mid1;
}
8.6.3.3.wqs二分優化dp\(O(dp*\log N)\)
-
\(f[i][x]\)：考慮前i個且恰好選了j個的最值\(\Rightarrow\)\(f[i]\)：考慮前i個且選了若干個的最值。
大大減少了復雜度。因此首先設的方程可以大膽設第二維。
\(f[i]\)使用struct類型儲存val：\(f[i]\)的值以及cnt：選了多少個物品。
然后根據前者的方程或后者的方程進行狀態轉移。前者的狀態轉移\(\xRightarrow{省略第二維}\)后者的狀態轉移。
-
用其他優化方法優化\(f[i]\)的dp，降低復雜度\(O(dp)\)。
-
套上wqs二分。
struct Wqs
{
int val,cnt;
Wqs operator + (const Wqs &qw) const
{
return {val+qw.val,cnt+qw.cnt};
}
bool operator < (const PLI &qw) const
{
if(val!=qw.val) return val<qw.val;
return cnt<qw.cnt;
}
}f[N]; //f[i]：考慮前i個且選了若干個的最值
//dp：考慮前i個且選了若干個的最值
void calc(int mid,int &cnt)
int l=-UP,r=UP;
int cnt;
while(l<r)
{
int mid=(l+r)>>1;
calc(mid,cnt);
if(cnt<=k) r=mid;
else l=mid+1;
}
calc(l,cnt);
printf("%lld\n",f[n].val-l*k);
8.7.dp套dp
適用條件：1.較難得知轉移到哪個狀態；2.根據當前的狀態以及轉移的方向求出可以轉移到哪些狀態也需要另一個dp求解；3.題目硬把\(dp_a\)套入\(dp_b\)，而\(dp_b\)的轉移必須根據\(dp_a\)的實際情況轉移狀態。
類似于自動機。
-
設計外層dp和內層dp。
外層dp負責求解當前問題，內層dp負責根據當前的狀態以及轉移的方向求出可以轉移到哪些狀態。
外層dp：
- 角度一：用足夠多的維度信息表示當前的狀態以供內層dp求出可以轉移到哪些狀態。
- 角度二：內層dp的值域小：直接把內層dp的值設為狀態。\(e.g.\)\(f_{i,v_0,v_1}\)：位置i的\(g_{i,0},g_{i,1}\)的值分別為\(v_0,v_1\)時的……。
-
優化狀態
一定不能腦測狀態數，以實際搜出來的結果為準。
dp套dp的瓶頸一般在于狀態數。
- 狀壓。
- 發現題目性質，實際有效的狀態數很少。
- 極小狀態集。
-
狀態轉移。一般采用由自己推別人。
-
內層dp根據當前的狀態以及轉移的方向求出可以轉移到哪些狀態。
如果外層dp直接把內層dp的值設為狀態，則狀態直接套用內層dp的方程得到應轉移到的狀態。
-
外層dp從當前的狀態轉移到內層dp的求出的狀態。
-
auto go[]={}; //轉移的方向
LL f[N][K]; //f[][state]：外層dp
LL g[N]; //內層dp
int dp(int state,auto ne){} //內層dp：根據當前的狀態state以及轉移的方向ne求出可以轉移到哪些狀態
//自己推別人，枚舉下一步轉移的方向進行轉移
for(int i=1;i<=n-1;i++)
for(int state=0;state<(1<<k);state++)
for(int j=0;j<m;j++)
{
int ne=dp(state,go[j]);
//外層dp從當前的狀態轉移到內層dp的求出的狀態
}
8.8.玄學優化
8.8.1.剪枝有效狀態數
適用條件：發現有效狀態數很少，但是不知道怎么排除無效狀態。
用vector存該輪的有效狀態，用該vector轉移到下一輪。這樣做可以做到接近正解。
e.g.\(f_{i,j}\)：不超過j個的最值。對于每個i，map存\([j,f_{i,j}]\)，即將到i+1時，把\(f_{i,j}\)劣于前綴最值的狀態刪除，不轉移給i+1。
8.8.2.線段樹剪枝
適用條件：優化\(O(N^2)\)暴力，且滿足像斜率優化dp、決策單調性等最優決策點很少的情況。
以\(f_i=\max\limits_{1≤j≤i-1\&\& a[j]≤a[i]}\{f_j+val(j,i)\}\)為例：正解做法是CDQ分治套斜率優化dp。
-
將原暴力套用線段樹，復雜度多一個\(O(\log)\)。
線段樹葉子節點維護dp下標。按照a[i]從小到大考慮i：依次遍歷線段樹葉子節點[1,i-1]求出\(f_i\)，然后把\(f_i\)插入到線段樹。
-
但是可以在線段樹上剪枝。
設計線段樹節點的估價函數=子樹最大的\(f_j\)+子樹最大的val(k,i)。注意\(f_j\)與val(k,i)是相對獨立的。
剪枝1：遍歷過程中，如果當前的\(f_i\)>即將遍歷的節點的估價函數，不用往下遍歷該節點。
剪枝2：優先遍歷估價函數大的兒子。這樣就有更大概率不用遍歷另一個兒子了。
注意：
- 當題目滿足滿足像斜率優化dp、決策單調性等最優決策點很少時，該做法相當于KD-Tree，不劣于\(O(N\sqrt N)\)，實際表現\(O(N\log^2 N)\)。
- 該技巧不局限于dp。
- 線段樹遍歷過程中，當j>=i時，val(j,i)的值要保證估價函數的正確性！！！
PLI a[N],best; //best：求f_i的遍歷過程中，當前最優的f_i
LL f[N];
struct Segmenttree
{
int l,r;
LL maxf; //子樹中最大的f
}tr[N*4];
void pushup(int u)
{
tr[u].maxf=max(tr[u<<1].maxf,tr[u<<1|1].maxf);
return ;
}
void build(int u,int l,int r)
{
tr[u]={l,r,LL(-1e18)};
if(l==r) return ;
int mid=(l+r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
return ;
}
void change(int u,int x,LL f)
{
if(tr[u].l==tr[u].r)
{
tr[u].maxf=f;
return ;
}
int mid=(tr[u].l+tr[u].r)>>1;
if(x<=mid) change(u<<1,x,f);
else change(u<<1|1,x,f);
pushup(u);
return ;
}
LL val(LL j,LL i)
{
if(j>=i) return ; //注意當j>=i時填寫的返回值要保證估價函數的正確性?。?！
return ;
}
void solve(int u,int l,int r)
{
if(tr[u].l==tr[u].r)
{
best.first=max(best.first,tr[u].maxf+val(tr[u].l,best.second));
return ;
}
int mid=(tr[u].l+tr[u].r)>>1;
LL fl=tr[u<<1].maxf+val(/*使得左子樹取到最大的val(k,best.second)的k*/,best.second),fr=tr[u<<1|1].maxf+val(/*使得右子樹取到最大的val(k,best.second)的k*/,best.second);
if(fr>=fl)
{
if(r>mid && fr>best.first) solve(u<<1|1,l,r);
if(l<=mid && fl>best.first) solve(u<<1,l,r);
}
else
{
if(l<=mid && fl>best.first) solve(u<<1,l,r);
if(r>mid && fr>best.first) solve(u<<1|1,l,r);
}
return ;
}
for(int i=1;i<=n;i++)
{
scanf("%lld",&a[i].first);
a[i].second=i;
}
sort(a+1,a+n+1);
build(1,0,n);
change(1,0,f[0]); //邊界
for(int i=1;i<=n;i++)
{
best={-1e18,a[i].second};
solve(1,0,a[i].second-1);
f[a[i].second]=best.first;
change(1,a[i].second,f[a[i].second]);
}
9.數據結構化dp
9.1.區間詢問——貓樹優化dp
9.2.修改——動態dp
矩陣常數大，可以只維護矩陣中有用的信息。
本質是帶修改的dp。當某一類dp的某一狀態要求修改時，我們可以用數據結構優化轉移，使修改后重新做一次dp的復雜度是\(O(c*\log N)\)。
- 寫出樸素dp方程。
- 根據方程選擇轉移方法：廣義矩陣乘法或數據結構
pushup
9.2.1.簡單的方程——廣義矩陣乘法中轉移
適用條件：形如\(f_i=(f_{i-1}\otimes a) \oplus f_{i-1} \oplus c\oplus \cdots\)，且\(\otimes\)對\(\oplus\)存在分配律。一般是\(f_i=\max \{ f_{i-1} +\cdots \}\)。方程能轉化成矩陣形式。
9.2.1.1.廣義矩陣乘法
對于一個lm的矩陣A與一個mn的矩陣B，定義廣義矩陣乘法AB=C的結果是一個ln的矩陣C，滿足二元運算\(\oplus\)和\(\otimes\)：\(C_{i,k}=(A_{i,1} \otimes B_{1,k}) \oplus (A_{i,2} \otimes B_{2,k}) \oplus \cdots \oplus (A_{i,m} \otimes B_{m,k})=\bigoplus\limits_{j=1}^{m}(A_{i,j}\otimes B_{j,k})\)。
當\(\otimes\)對\(\oplus\)存在分配律（即\((\bigoplus a) \otimes b = \bigoplus (a \otimes b)\)）且\(\oplus\)滿足交換律和結合律時，我們定義的廣義矩陣乘法滿足結合律。
-
證明
\(((A*B)*C)_{i,l}=\bigoplus\limits_{k=1}((A*B)_{i,k} \otimes C_{k,l})=\bigoplus\limits_{k=1}((\bigoplus\limits_{j=1}(A_{i,j}\otimes B_{j,k}))\otimes C_{k,l})\)
\((A*(B*C))_{i,l}=\bigoplus\limits_{j=1}(A_{i,j}\otimes (B*C)_{j,l})=\bigoplus\limits_{j=1}(A_{i,j} \otimes (\bigoplus\limits_{k=1}(B_{j,k}\otimes C_{k,l})))\)
當滿足\((\bigoplus a) \otimes b = \bigoplus (a \otimes b)\)時：
\(((A*B)*C)_{i,l}=\bigoplus\limits_{k=1}\bigoplus\limits_{j=1}(A_{i,j}\otimes B_{j,k}\otimes C_{k,l})=\bigoplus\limits_{j=1}\bigoplus\limits_{k=1}(A_{i,j} \otimes B_{j,k}\otimes C_{k,l})\)
\((A*(B*C))_{i,l}=\bigoplus\limits_{j=1}\bigoplus\limits_{k=1}(A_{i,j} \otimes B_{j,k}\otimes C_{k,l})\)
\(\therefore ((A*B)*C)_{i,l}=(A*(B*C))_{i,l}\)
同時，加法\(+\)對最值\(\min / \max\)存在分配律：\(\max / \min \{ a,b \}+c = \max / \min \{ a+c,b+c \}\)。因此我們可以定義廣義矩陣乘法\(C_{i,k}=\max\limits_j / \min\limits_j \{ A_{i,j}+B_{j,k} \}\)。之前學過的\(Floyd\)算法就是這種廣義矩陣乘法：\(f_{i,k}=\max\limits_j / \min\limits_j \{ f_{i,j}+f_{j,k} \}\)。
補充：關于位運算的結合律的證明：
因為位運算是按位運算，所以只要一位滿足結合律，則該位運算就滿足結合律。
廣義矩陣乘法具有結合律是實現動態dp的必要條件。
9.2.1.2.動態線性dp
下面以帶修改的最大子段和為例：
參與中間運算的矩陣應memset(0)以不造成影響。
強制令矩陣中某一位置\(mat[x][y]\)不參與運算：mat[x][y]=-INF;
-
根據方程\(f\)設計轉移矩陣\(G\)。
-
設計\(G\)
有樸素方程：對于一個詢問\([l,r]\)，\(f_i\)：以\(a_i\)結尾的\([l,i]\)的最大子段和，\(g_i\)：\([l,i]\)的最大子段和，\(f_i=\max \{ f_{i?1}+a_i,a_i \},g_i=\max \{ g_{i?1},f_i \}\)：
\(\begin{bmatrix} f_{i-1} & g_{i-1} \end{bmatrix} * \begin{bmatrix} a_i & \\ & \end{bmatrix}=\begin{bmatrix} f_i & g_i \end{bmatrix}\)
當發現沒有空間寫不下去的時候，不妨再來一維0：\(\begin{bmatrix} f_{i-1} & g_{i-1} & 0 \end{bmatrix}*\begin{bmatrix} a_i & & -\infty \\ -\infty & & -\infty \\ a_i & & 0 \end{bmatrix}=\begin{bmatrix} f_i & g_i & 0 \end{bmatrix}\)
\(g_i=\max \{ g_{i?1},f_i \}\)不好處理，可以把\(f_i\)拆開：\(g_i=\max \{ g_{i?1},f_{i-1}+a_i,a_i \}\)：\(\begin{bmatrix} f_{i-1} & g_{i-1} & 0 \end{bmatrix}*\begin{bmatrix} a_i & a_i & -\infty \\ -\infty & 0 & -\infty \\ a_i & a_i & 0 \end{bmatrix}=\begin{bmatrix} f_i & g_i & 0 \end{bmatrix}\)
每一個i對應著自己的一個轉移矩陣\(G_i\)。
- 修改\(a_i\)。更新對應的\(G_i\)中的某些元素。
- 詢問\([l,r]\)的最大子段和。求出\(G_l\)到\(G_r\)的矩陣“乘積”。因為我們定義的廣義矩陣乘法具有結合律，因此可以用線段樹維護區間矩陣“乘積”。
-
-
根據方程\(f\)和轉移矩陣\(G\)設計初始向量\(F_0\)，以在區間矩陣乘積中找到答案。
-
\(F_0\)的意義
當我們對于一個詢問\([l,r]\)求出區間矩陣乘積時，區間矩陣乘積的實際含義是（注意此時\(f_i\)對于一個詢問\([l,r]\)表示以\(a_i\)結尾的\([l,i]\)的最大子段和，\(g_i\)同理）\(\begin{bmatrix} f_{l-1} & g_{l-1} & 0 \end{bmatrix}*\begin{bmatrix} a_i & a_i & -\infty \\ -\infty & 0 & -\infty \\ a_i & a_i & 0 \end{bmatrix}=\begin{bmatrix} f_r & g_r & 0 \end{bmatrix}\)。其中\(f_{l-1}\)和\(g_{l-1}\)是沒有意義的，既然初始向量\(F_0\)沒有意義，那么轉移矩陣\(G\)和答案向量\(F_{ans}\)的正確性也無法保證。
實際上，只要設計出一個初始向量\(F_0\)，對于任意的起點l，都有\(F_0*G_l=f_l\)，那么動態dp的正確性即可達到保證。證明：廣義矩陣乘法的結合律。
-
設計\(F_0\)
在草稿紙上簡單模擬可設計出一個初始向量\(F_0\)：\(\begin{bmatrix} 0 & -\infty & 0 \end{bmatrix}\)。因為對于任意的起點l，都有\(\begin{bmatrix} 0 & -\infty & 0 \end{bmatrix}*\begin{bmatrix} a_l & a_l & -\infty \\ -\infty & 0 & -\infty \\ a_l & a_l & 0 \end{bmatrix}=\begin{bmatrix} f_l & g_l & 0 \end{bmatrix}\)。
除此之外，\(\begin{bmatrix} -\infty & -\infty & 0 \end{bmatrix}\)也是合法的初始向量\(F\)。但是\(\begin{bmatrix} 0 & 0 & 0 \end{bmatrix}\)不是合法的初始向量\(F\)，因為\(a_i\)可以為負數。
由\(F_0*G=F_{ans}\)得：\(\begin{bmatrix} 0 & -\infty & 0 \end{bmatrix}*\begin{bmatrix} a & b & c \\ d & e & f \\ g & h & i \end{bmatrix}=\begin{bmatrix} \max \{ a,g \} & \max \{ b,h \} & \max \{ c,i \} \end{bmatrix}\)
又因為方程\(g_r\)是最終的答案，所以當我們得到區間矩陣乘積\(G\)后，\(ANS=\max \{ G[0][1],G[2][1] \}\)。（如果\(F_0=\begin{bmatrix} -\infty & -\infty & 0 \end{bmatrix}\)，\(ANS=G[2][1]\) ，用廣義矩陣乘法的結合律可證兩個答案都是正確的）
-
-
線段樹維護區間矩陣乘積。
//廣義矩陣乘法
struct Matrix
{
int mat[3][3]; //矩陣
Matrix(){memset(mat,0,sizeof mat);} //當Matrix res;時，對res進行下面的初始化
Matrix(int a) //當res=Matrix(a);時，對res進行下面的初始化
{
mat[0][0]=mat[0][1]=mat[2][0]=mat[2][1]=a;
mat[0][2]=mat[1][0]=mat[1][2]=-INF;
mat[1][1]=mat[2][2]=0;
}
Matrix operator * (const Matrix &qw) const //定義的廣義矩陣乘法
{
Matrix res;
memset(res.mat,-0x3f,sizeof res.mat);
for(int k=0;k<3;k++)
for(int i=0;i<3;i++)
for(int j=0;j<3;j++)
res.mat[i][j]=max(res.mat[i][j],mat[i][k]+qw.mat[k][j]);
return res;
}
int get_max() //根據初始向量F0和區間轉移矩陣乘積，在區間矩陣乘積中找答案
{
return max(mat[0][1],mat[2][1]);
}
};
struct Tree
{
int l,r;
Matrix G;
}tr[N*4]; //線段樹開4倍！！！
//當前節點的區間矩陣乘積=左兒子*右兒子
void pushup(int u)
{
tr[u].G=tr[u<<1].G*tr[u<<1|1].G;
return ;
}
void build(int u,int l,int r)
{
tr[u]={l,r};
if(l==r)
{
int a;
scanf("%d",&a);
tr[u].G=Matrix(a);
return ;
}
int mid=(l+r)>>1;
build(u<<1,l,mid);
build(u<<1|1,mid+1,r);
pushup(u);
return ;
}
void change(int u,int x,int val)
{
if(tr[u].l==tr[u].r)
{
tr[u].G=Matrix(val); //單點修改時找到線段樹對應的單點，修改矩陣的某些元素
return ;
}
int mid=(tr[u].l+tr[u].r)>>1;
if(x<=mid) change(u<<1,x,val);
else change(u<<1|1,x,val);
pushup(u);
return ;
}
Matrix query(int u,int l,int r)
{
if(l<=tr[u].l && tr[u].r<=r) return tr[u].G;
int mid=(tr[u].l+tr[u].r)>>1;
//注意下面的書寫，因為矩陣乘法沒有交換律?。?！
if(l<=mid && r>mid) return query(u<<1,l,r)*query(u<<1|1,l,r);
else
{
if(l<=mid) return query(u<<1,l,r);
else return query(u<<1|1,l,r);
}
}
build(1,1,n);
//單點修改權值
scanf("%d%d",&x,&val);
change(1,x,val);
//區間詢問最大子段和
scanf("%d%d",&l,&r);
Matrix res=query(1,l,r);
printf("%d\n",res.get_max());
9.2.1.3.動態樹形dp
9.2.1.3.1.子結點的信息與當前節點是加和關系，具有可加減性
下面以帶修改的樹上最大點權獨立集為例：
-
子樹方程、答案。
-
子樹方程
\(f[u][bool]\)：以u為根的子樹，u選不選時的最大點權獨立集權值。
動態dp需要維護序列的數據結構，動態樹形dp自然需要把樹剖分成重鏈轉換為序列問題。因此還需要額外設計出與重鏈無關（也就是輕兒子）的信息的方程以方便后面維護和轉移。這樣當前節點=重兒子（與其在同一條重鏈上，轉化為序列）+輕兒子。
-
-
設計方程分離出輕兒子的信息、轉移。
-
輕兒子方程
\(g[u][bool]\)：不包含u所在的重鏈部分（但是包含u）的以u為根的子樹，u選不選時的最大點權獨立集權值。
注意求g時先把所有兒子的貢獻算上，再減去重兒子求出g，注意是自頂向下的遞推！否則會少減son[son[u]]或多減son[son[v]]！??！
-
-
狀態轉移：設\(son[u]\)為u的重兒子。用\(g[u]\)和\(f[son[u]]\)寫出\(f[u]\)的轉移方程。
-
狀態轉移
\(g[u][0]=\sum\limits_{v ≠ son[u]} \max \{ f[v][0],f[v][1] \}\)，\(g[u][1]=\sum\limits_{v ≠ son[u]} \{ f[v][0]+a[u] \}\)。
用\(g[u]\)和\(f[son[u]]\)寫出\(f[u]\)的轉移方程：\(f[u][0]=g[u][0]+\max \{ f[son[u]][0],f[son[u]][1] \}\)，\(f[u][1]=g[u][1]+f[son[u]][0]\)。
-
-
轉換成矩陣形式。
-
矩陣形式
\(\begin{bmatrix} f[son[u]][0]&f[son[u]][1] \end{bmatrix} \times \begin{bmatrix} g[u][0]&g[u][1]\\ g[u][0]&-\infin \end{bmatrix} = \begin{bmatrix} f[u][0]&f[u][1] \end{bmatrix}\)
但是，樹上序列一般是以根節點在前，葉子節點在后，所以矩陣乘積自然是從根節點的矩陣連乘到葉子節點的矩陣：\(G_{root}*...*G_u*G_{son}*F_{son}\)。因此我們需要利用矩陣的轉置運算律\((AB)^T=B^TA^T\)來交換成正確的順序：\(\begin{bmatrix} g[u][0] & g[u][0] \\ g[u][1] & -\infty \end{bmatrix} \times \begin{bmatrix} f[son[u]][0] \\ f[son[u]][1] \end{bmatrix} = \begin{bmatrix} f[u][0]\\ f[u][1] \end{bmatrix}\)。
-
-
求解。
初始向量\(F_0\)：因為對于任意一個葉子節點u，有\(\begin{bmatrix}g[u][0]&g[u][0]\\ g[u][1]&-\infin\end{bmatrix}\times\begin{bmatrix}0\\ 0\end{bmatrix}=\begin{bmatrix}f[u][0]\\ f[u][1]\end{bmatrix}\)（注意此處的g是轉移方程），所以初始向量是\(\begin{bmatrix}0\\0\end{bmatrix}\)。
答案向量\(F_{ans}\)：由初始向量和轉移矩陣\(**G**\)推得：\(f[u][0]=\max(g[0][0],g[0][1]),f[u][1]=\max(g[1][0],g[1][1])\)。
\(ans=\max(f[1][0],f[1][1])=\max \{ g[0][0],g[0][1],g[1][0],g[1][1] \}\)
總結
設計兩個方程：子樹方程和輕兒子方程。
答案向量\(F_{root}\)是根節點所在重鏈（簡記“根重鏈”）的區間轉移矩陣乘積\(G\)****乘初始矩陣，其他重鏈的鏈頂的矩陣\(**F_{top}**\)（其重鏈的區間矩陣乘積\(**G**\)乘初始矩陣）作為輕兒子更新在根重鏈上的父節點的****轉移方程\(**g**\)。
轉移矩陣\(**G**\)由輕兒子轉移方程\(**g**\)構成。區間矩陣乘積\(**G**\)是單點矩陣\(**poi**\)的連乘積，單點矩陣\(**poi**\)是由轉移方程\(**g**\)構成的，當轉移方程\(**g**\)被修改時，單點矩陣\(**poi**\)要及時更新poi[x]=Matrix(g[x][0],g[x][1]);，區間矩陣乘積\(**G**\)也要及時更新change(1,id[x]);（樹剖線段樹）或pushup(x);（全局平衡二叉樹）。
在modify_path(pos,val)（樹剖線段樹）和modify(pos,val)（全局平衡二叉樹）中：首先在原樹上單點修改posa[pos]=val。然后更新從u到根節點的信息：隨著u=fa[top[u]]的過程中，對于每一輪循環：****1.記錄線段樹（或平衡樹，下同）的原先信息：區間矩陣乘積；2.用原樹的信息來更新線段樹的信息；3.記錄線段樹的當前信息：區間矩陣乘積；4.用原先信息和當前信息（作為輕兒子區間矩陣乘積）更新原樹（而不是線段樹）的鏈頂父節點的信息。
9.2.1.3.1.1.重鏈剖分+線段樹\(O(N \log^2 N)\)
類似于線段樹維護動態dp和重鏈剖分板子。
由于要詢問一整條重鏈上的矩陣乘積，因此還需要記錄\(ed[i]\)：重鏈的末尾的原編號。
需要注意的地方是modify_path(pos,val)：
- 修改單點時要把其所在的重鏈（作為鏈頂的父節點的輕子樹）到根節點所在的重鏈的信息全部更新。
- 修改單點時加偏移量而不是直接賦值，因為其還包含其他輕兒子的信息。
- 當轉移方程\(g\)被修改時，單點矩陣\(poi\)要及時更新
poi[x]=Matrix(g[x][0],g[x][1]);，區間矩陣乘積\(G\)也要及時更新change(1,id[x]);。 - 向上跳一條重鏈時，因為更新了輕子樹的區間乘積，所以要更新其父節點的轉移方程\(g\)。
int n,m;
int a[N];
int h[N],e[M],ne[M],idx;
int g[N][2];
struct Matrix
{
int mat[2][2];
Matrix(int gu0,int gu1)
{
mat[0][0]=mat[0][1]=gu0;
mat[1][0]=gu1;
mat[1][1]=-INF;
}
int get_max()
{
return max(max(mat[0][0],mat[0][1]),max(mat[1][0],mat[1][1]));
}
}poi[N]; //point：單點矩陣
struct Tree
{
int l,r;
Matrix G;
}tr[N*4];//線段樹開4倍?。。?int id[N],nid[N],cnt; //id:節點的dfn序編號；nid[id[i]]：id[i]->i的映射
int dep[N],siz[N],top[N],ed[N],fa[N],son[N]; //ed[top]:重鏈的末尾的原編號；
//預處理樹剖+g先把所有兒子的貢獻算上，到dfs2再減去重兒子
void dfs1(int u,int father,int depth)
{
dep[u]=depth,fa[u]=father,siz[u]=1;
g[u][1]=a[u];
for(int i=h[u];i!=0;i=ne[i])
{
int v=e[i];
if(v==father) continue;
dfs1(v,u,depth+1);
siz[u]+=siz[v];
if(siz[son[u]]<siz[v]) son[u]=v;
g[u][1]+=g[v][0];
g[u][0]+=max(g[v][0],g[v][1]);
}
//不能在這里直接減去重兒子求g，因為這里是自底向上的遞推
return ;
}
//做剖分（t是重鏈的頂點）
//減去重兒子求出g，注意是自頂向下的遞推！否則會少減son[son[u]]或多減son[son[v]]?。?！
void dfs2(int u,int t)
{
id[u]=++cnt,nid[cnt]=u,top[u]=t,ed[t]=u;
g[u][0]-=max(g[son[u]][0],g[son[u]][1]);
g[u][1]-=g[son[u]][0];
poi[u]=Matrix(g[u][0],g[u][1]);
if(son[u]==0) return ;
dfs2(son[u],t);
for(int i=h[u];i!=0;i=ne[i])
{
int v=e[i];
if(v==fa[u] || v==son[u]) continue;
dfs2(v,v);
}
return ;
}
void build(int u,int l,int r)
{
if(l==r)
{
tr[u].G=poi[nid[l]]; //把單點矩陣復制到線段樹對應的單點
return ;
}
}
void change(int u,int x)
{
if(tr[u].l==tr[u].r)
{
tr[u].G=poi[nid[x]];
return ;
}
}
void modify_path(int x,int y){
//在原樹上單點修改
g[x][1]+=y-a[x]; //注意加偏移量而不是直接賦值y，因為g還包含其他輕兒子的信息
poi[x].mat[1][0]+=y-a[x]; //g和poi要同時改?。?！
a[x]=y;
Matrix bef,aft;
while(x!=-1)//直到x到根節點
{
//記錄線段樹的原先信息：區間矩陣乘積
bef=query(1,id[top[x]],id[ed[top[x]]]);
//用原樹的信息來更新線段樹的信息
change(1,id[x]); //因為上一輪循環更新了單點矩陣poi，所以這里要更新區間矩陣乘積g
//記錄線段樹的當前信息：區間矩陣乘積
aft=query(1,id[top[x]],id[ed[top[x]]]);
//用原先信息和當前信息（作為輕兒子區間矩陣乘積）更新原樹（而不是線段樹）的鏈頂父節點的信息
x=fa[top[x]]; //跳到上面一條重鏈
if(x==-1) break; //因為是一直跳到根節點，fa[1]=-1
//因為更新了輕子樹的區間乘積，所以這里要更新其父節點的轉移方程g
g[x][0]+=max(max(aft.mat[0][0],aft.mat[0][1]),max(aft.mat[1][0],aft.mat[1][1]))-max(max(bef.mat[0][0],bef.mat[0][1]),max(bef.mat[1][0],bef.mat[1][1]));
g[x][1]+=max(aft.mat[0][0],aft.mat[0][1])-max(bef.mat[0][0],bef.mat[0][1]);
//因為更新了轉移方程g，因此這里要更新單點矩陣poi
poi[x]=Matrix(g[x][0],g[x][1]);
}
return ;
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<n;i++)
{
int u=read(),v=read();
add(u,v),add(v,u);
}
dfs1(1,-1,1);
dfs2(1,1);
build(1,1,n);
while(m--)
{
int x=read(),y=read();
modify_path(x,y);
Matrix res;
res=query(1,id[1],id[ed[1]]);
printf("%d\n",res.get_max());
}
return 0;
}
9.2.1.3.1.2.全局平衡二叉樹\(O(N \log N)\)
適用范圍小，目前只出現在動態樹形dp\(O(N \log N)\)。
因為它與重鏈相關，因此它可以很好地配合動態樹形dp。
dfs_son(u,fa)求出重兒子，一開始就把輕重邊劃分好。順便先預處理\(g\):先把所有兒子的貢獻算上，到dfs再減去重兒子。dfs_g(u,fa)減去重兒子求出\(g\)，注意是自頂向下的遞推！build_subtree(u,fa)先把一條重鏈上的其他所有輕兒子子樹往下遞歸建樹build_subtree(light_son,u)，順便記錄輕兒子是其所在重鏈的頂端。再對這條重鏈建二叉樹build_chain(1,sidx)。返回重鏈的二叉樹的根節點return build_chain(1,sidx);。因為我們把樹剖分成重鏈，而根節點所在重鏈又會被建二叉樹，因此樹高是\(O(\log N)\)級別。build_chain(l,r)找重心保證復雜度，令重心為二叉樹的根節點，遞歸二叉樹左右兒子kid[u][0]=build_chain(l,i-1);kid[u][1]=build_chain(i+1,r);此時樹形結構確定，pushup(u)并返回重鏈的二叉樹的根節點。pushup(u)子樹矩陣乘積=左子樹矩陣乘積當前節點矩陣右子樹矩陣乘積（注意順序因為廣義矩陣乘法沒有交換律）modify(pos,val)先修改\(g[pos][1]\)（注意是加偏移量而不是直接賦值val，因為\(g\)還包含其他輕兒子的信息）并更新單點矩陣\(poi[pos]\)，然后一級一級向上跳更新其父親的子樹矩陣乘積\(sub[fa]\)（因為建樹時已保證樹高是\(O(\log N)\)級別，因此修改復雜度也是\(O(\log N)\)。當到達一條重鏈的鏈頂時（同時也是其父節點的輕兒子），要更新其父節點的\(g[fa][0]\)和\(g[fa][1]\)。
modify(pos,val)的注意事項同重鏈剖分modify_path(pos,val)****一樣。
int son[N],siz[N];
int seq[N],sidx; //記錄重鏈輔助build_chain
struct Matrix{}poi[N],sub[N]; //point：單點矩陣；subtree：子樹矩陣乘積
int root;
int fa[N],kid[N][2]; //全局平衡二叉樹的父節點和2個重子結點（注意不包含輕子節點）
bool top[N]; //是否是重鏈的頂端（同時也是其父節點的輕子節點）。不必記錄整棵樹的根節點為true，因為用不到
//求出重兒子，一開始就把輕重邊劃分好。g先把所有兒子的貢獻算上，到dfs_g再減去重兒子
void dfs_son(int u,int father)
{
siz[u]=1;
g[u][1]=a[u];
for(int i=h[u];i!=0;i=ne[i])
{
int v=e[i];
if(v==father) continue;
dfs_son(v,u);
siz[u]+=siz[v];
if(siz[v]>siz[son[u]]) son[u]=v;
g[u][1]+=g[v][0];
g[u][0]+=max(g[v][0],g[v][1]);
}
//不能在這里直接減去重兒子求g，因為這里是自底向上的遞推
return ;
}
//減去重兒子求出g，注意是自頂向下的遞推！否則會少減son[son[u]]或多減son[son[v]]?。?！
void dfs_g(int u,int father)
{
g[u][0]-=max(g[son[u]][0],g[son[u]][1]);
g[u][1]-=g[son[u]][0];
poi[u]=Matrix(g[u][0],g[u][1]);
for(int i=h[u];i!=0;i=ne[i])
{
int v=e[i];
if(v==father) continue;
dfs_g(v,u);
}
return ;
}
//子樹矩陣乘積=左子樹矩陣乘積*當前節點矩陣*右子樹矩陣乘積（注意順序因為廣義矩陣乘法沒有交換律）
void pushup(int u)
{
sub[u]=poi[u];
if(kid[u][0]) sub[u]=sub[kid[u][0]]*sub[u];
if(kid[u][1]) sub[u]=sub[u]*sub[kid[u][1]];
return ;
}
//返回重鏈的二叉樹的根節點
int build_chain(int l,int r)
{
if(l>r) return 0;
//預處理找重心
int wtot=0,wi=0; //總權值
for(int i=l;i<=r;i++)
{
int u=seq[i];
wtot+=siz[u]-siz[son[u]];
}
for(int i=l;i<=r;i++)
{
int u=seq[i];
wi+=siz[u]-siz[son[u]]; //當前點的權值
if((wi<<1)>=wtot) //只要當前點的權值大于等于一半的總權值即可選其為重心，降低復雜度
{
kid[u][0]=build_chain(l,i-1);
kid[u][1]=build_chain(i+1,r);
fa[kid[u][0]]=fa[kid[u][1]]=u;
pushup(u);
return u; //返回重鏈的二叉樹的根節點，一定會有一個點返回
}
}
}
//返回重鏈的二叉樹的根節點
int build_subtree(int u,int father)
{
//不可以直接在這里top[u]=true，因為下面還要對這條重鏈做處理，當前的u不一定是鏈頂
for(int uu=u;uu!=0;father=uu,uu=son[uu])
for(int i=h[uu];i!=0;i=ne[i])
{
int v=e[i];
if(v==father || v==son[uu]) continue;
int light_son=build_subtree(v,uu); //輕兒子同時也是下一條新重鏈的鏈頂
top[light_son]=true;
fa[light_son]=uu;
}
sidx=0;
for(int uu=u;uu!=0;uu=son[uu]) seq[++sidx]=uu;
return build_chain(1,sidx);
}
void modify(int x,int y)
{
g[x][1]+=y-a[x]; //注意加偏移量而不是直接賦值y，因為g還包含其他輕兒子的信息
poi[x]=Matrix(g[x][0],g[x][1]);//g和poi要同時改！??！
a[x]=y;
int befsub0,befsub1,aftsub0,aftsub1;
while(x)//直到x到根節點
{
if(top[x])
{
//記錄平衡樹的原先信息：區間矩陣乘積
befsub0=max(sub[x].mat[0][0],sub[x].mat[0][1]);
befsub1=max(sub[x].mat[1][0],sub[x].mat[1][1]);
}
//用原樹的信息來更新平衡樹的信息
pushup(x);//因為上一輪循環更新了單點矩陣poi，所以這里要更新區間矩陣乘積g
if(top[x])
{
//記錄平衡樹的當前信息：區間矩陣乘積
aftsub0=max(sub[x].mat[0][0],sub[x].mat[0][1]);
aftsub1=max(sub[x].mat[1][0],sub[x].mat[1][1]);
//用原先信息和當前信息（作為輕兒子區間矩陣乘積）更新原樹（而不是平衡樹）的父節點的信息
//因為更新了輕子樹的區間乘積，所以這里要更新其父節點的轉移方程g
g[fa[x]][0]+=max(aftsub0,aftsub1)-max(befsub0,befsub1);
g[fa[x]][1]+=aftsub0-befsub0;
//因為更新了轉移方程g，因此這里要更新單點矩陣poi
poi[fa[x]]=Matrix(g[fa[x]][0],g[fa[x]][1]);
}
x=fa[x];
}
}
int main()
{
n=read(),m=read();
for(int i=1;i<=n;i++) a[i]=read();
for(int i=1;i<n;i++)
{
int u=read(),v=read();
add(u,v),add(v,u);
}
dfs_son(1,-1);
dfs_g(1,-1);
root=build_subtree(1,-1);
int lastans=0;
while(m--)
{
int x=read(),y=read();
x^=lastans;
modify(x,y);
lastans=sub[root].get_max();
printf("%d\n",lastans);
}
return 0;
}
9.2.1.3.2.子結點的信息與當前節點是最值關系
設計一個重鏈方程。
若有方程\(g_u\)表示一條重鏈上的最值，顯然\(ANS=\max \{ 所有重鏈 \}\)，則開一個全局multiset<int> ans來維護\(g_u\)的最大值得到答案。
若輕兒子在父節點矩陣中作為元素\(maxn\)或\(smaxn\)（節點u所有的兒子v中最大或次大的\(f_v\)），則對于每一個節點開一個multiset<int> h來維護\(maxn\)或\(smaxn\)。
初始時，要把初值放進所有的multiset，因為后面會multiset.erase()。
總結
設計一個方程：重鏈方程。
答案是所有重鏈的區間矩陣乘積的最大值，我們開一個全局multiset<int> ans來維護重鏈的區間矩陣乘積的最大值得到答案。一個重鏈的鏈頂的矩陣\(**F_{top}**\)（其重鏈的區間矩陣乘積\(**G**\)乘初始矩陣）作為輕兒子更新其父節點的multiset<int> h來維護父節點的單點矩陣中的元素\(maxn\)或\(smaxn\)。
轉移矩陣\(**G**\)由輕兒子的最值\(maxn\)或\(smaxn\)構成。區間矩陣乘積\(**G**\)是單點矩陣\(**poi**\)的連乘積，單點矩陣\(**poi**\)的組成成分之一是輕兒子的最值\(maxn\)或\(smaxn\)，也就是每個點的multiset<int> h。當輕兒子的最值\(maxn\)或\(smaxn\)被修改時，每個點的multiset<int> h要及時更新h[u].erase(h[u].find(f_bef));h[u].insert(f_aft);，區間矩陣乘積\(**G**\)也要及時更新change(1,id[x]);（樹剖線段樹）或pushup(x);（全局平衡二叉樹）。
在modify_path(pos,val)（樹剖線段樹）和modify(pos,val)（全局平衡二叉樹）中：首先在原樹上單點修改posa[pos]=val。然后更新從u到根節點的信息：隨著u=fa[top[u]]的過程中，對于每一輪循環：1.記錄線段樹（或平衡樹，下同）的原先信息：區間矩陣乘積；2.用原樹的信息來更新線段樹的信息；3.記錄線段樹的當前信息：區間矩陣乘積；4.用原先信息和當前信息（作為輕兒子區間矩陣乘積）更新原樹（而不是線段樹）的鏈頂父節點的信息及全局ansans.erase(ans.find(gbe));ans.insert(gaf);****。
9.2.1.3.3.區間修改
9.2.1.3.3.1.區間的矩陣修改
一般題目的矩陣都有特殊性質：在兩個單點矩陣的\(mat[x][y]\)都加上一個值后，它們的矩陣乘積也只有在\(mat[x][y]\)加上一倍的這個值。這樣的話我們可以用懶標記維護它。
下面假設mat[x][y]的x=1，y=0。
struct Tree{LL val1;/*區間加val1懶標記*/}tr[N*4];
//給當前的節點u加上懶標記
void eval(int u,LL val1)
{
tr[u].val1+=val1;
tr[u].G.mat[1][0]+=val1; //經過在草稿紙上手動模擬，發現懶標記只要加在矩陣的這些位置即可
return ;
}
//其他部分基本等同于線段樹的懶標記操作
//詢問和其他修改也要記得pushdown
void change_val2(){pushdown(u);}
Matrix query(int u,int l,int r){pushdown(u);/*別忘記這里?。?！*/}
9.2.1.3.3.2.樹上的路徑修改
對于“在路徑(u,v)上的每一個點（或邊）增加一個權值w”，采用樹上差分的方法：設函數add_val1(u,w)：把從u到根節點的路徑上的所有點的val1加w。只需要int p=lca(u,v);add(u,w),add(v,w),add(p,-w),add(fa[p],-w)即可。
9.2.2.復雜的方程——數據結構pushup()中轉移
當dp方程過于復雜或是矩陣維度過大，且dp的狀態與區間長度無關、dp狀態的值域較小時，采用數據結構優化，dp在pushup中執行。
設計dp時要注意dp的狀態要與區間長度無關，常見設計的dp狀態如下：
-
\(f[W]\)：有W個……的……，其中W是較小的值域，則一次操作的復雜度是\(O(F(W)*\log N)\)。
-
選定一個子序列或劃分序列的問題：\(f[l][r]\)：區間dp，其中l,r≤W，W是較小的值域，則一次操作的復雜度是\(O(W^3*\log N)\)。
轉移：
線段樹+選定一個子序列的問題： $f[l][r]$：當前線段樹區間選定子序列[l,r]的……。$f[l][l]$在`build()`和`change()`中的葉子節點處理好。$f[l][r]$在`pushup()`中執行區間dp轉移： $f[l][r]=\max(lson[l][r],rson[l][r])$ $f[l][r]=\max\limits_{l≤k<r}\{lson[l][k]\oplus rson[k+1][r]\}$ 平衡樹+劃分序列的問題： $f_{point}[l][r]$：當前的節點在[l,r]的……。在新建節點時處理好。 $f_{segment}[l][r]$：當前的整棵子樹在[l,r]的……。在`pushup()`中執行區間dp轉移： $res[l][r]=\max\limits_{l≤k≤r}\{lson_{f_{segment}}[l][k]\oplus f_{point}[k][r]\}$ $f_{segment}[l][r]=\max\limits_{l≤k≤r}\{res[l][k]\oplus rson_{f_{segment}}[k][r]\}$區間詢問：
線段樹：開一個全局ans[W][W]。在`query()`中的`if(l≤tr[u].l && tr[u].r≤r)`加入貢獻： 新建res[W][W]。防止重復加入貢獻。 $res[l][r]=\max(ans[l][r],f[l][r])$ $res[l][r]=\max\limits_{l≤k<r}\{ans[l][k]\oplus f[k+1][r]\}$。因為遞歸一定是左兒子優先，所以可以從左到右加入貢獻。 ans←res
9.2.2.1.序列長度不變——線段樹維護
可修改權值。
每個區間開一個dp\(f[]\)，其中f[]省略了區間的這一維度（完整版是f[tr[u].l][tr[u].r][]）。
- pushup：
void pushup(int u)
{
Tree &p=tr[u],&ls=tr[u<<1],&rs=tr[u<<1|1];
memset(p.f,0,sizeof p.f);
for(int i=0;i<=min(c,p.r-p.l+1);i++)//階段：有i個人去A國
for(int l=max(0,i-(rs.r-rs.l+1));l<=min(i,ls.r-ls.l+1);l++)
{
int r=i-l;//l、r：狀態+決策：左右區間各去多少個人去A國
p.f[i]=(p.f[i]+(ls.f[l]*rs.f[r])%MOD)%MOD;
}
return ;
}
9.2.2.2.序列長度改變——平衡樹維護
可修改權值、插入刪除。
每個點開一個dp\(f[]\)，其中f[]代表整棵子樹中序遍歷的區間的信息。
-
pushup：
\(fpoint[l][r]\)：當前的節點在工作狀態[l,r]的范圍內的最大能量。
區間dp轉移：\(f_{point}[l][r]=\max\limits_{i≤k≤j}\{f_{point}[l][k]+f_{point}[k+1][r]\}\)
\(fsegment[l][r]\)：當前的整棵子樹在工作狀態[l,r]的范圍內的最大能量。
區間dp轉移：
\(res[l][r]=\max\limits_{l≤k≤r}\{lson_{f_{segment}}[l][k]+f_{point}[k][r]\}\)
\(f_{segment}[l][r]=\max\limits_{l≤k≤r}\{res[l][k]+rson_{f_{segment}}[k][r]\}\)
void pushup(int p)
{
if(ls) tr[p].lsiz=tr[ls].lsiz;
else tr[p].lsiz=tr[p].cnt;
tr[p].siz=tr[ls].siz+tr[rs].siz+tr[p].cnt;
memset(tr[idx].f_p,0,sizeof tr[idx].f_p);
tr[idx].f_p[0][0]=tr[idx].f_p[3][3]=tr[idx].a*tr[idx].cnt;
tr[idx].f_p[1][1]=tr[idx].b*tr[idx].cnt;
tr[idx].f_p[2][2]=tr[idx].c*tr[idx].cnt;
for(int len=2;len<=4;len++)
for(int l=0;l+len-1<4;l++)
{
int r=l+len-1;
for(int k=l;k<r;k++) tr[idx].f_p[l][r]=max(tr[idx].f_p[l][r],max(tr[idx].f_p[l][k],tr[idx].f_p[k+1][r]));
}
LL res[4][4];
memset(res,0,sizeof res);
for(int len=1;len<=4;len++)
for(int l=0;l+len-1<4;l++)
{
int r=l+len-1;
for(int k=l;k<=r;k++) res[l][r]=max(res[l][r],tr[ls].f_s[l][k]+tr[p].f_p[k][r]);
}
memset(tr[p].f_s,0,sizeof tr[p].f_s);
for(int len=1;len<=4;len++)
for(int l=0;l+len-1<4;l++)
{
int r=l+len-1;
for(int k=l;k<=r;k++) tr[p].f_s[l][r]=max(tr[p].f_s[l][r],res[l][k]+tr[rs].f_s[k][r]);
}
例題
《實踐.錯題本2022.3.18.【帶修改的dp——線段樹優化】Travel、2022.5.3.【帶修改的dp——平衡樹優化】噴式水戰》
浙公網安備 33010602011771號