[0.x]前言

参考书目：《算法竞赛进阶指导》

语言：[算法] 动规专题 - 图1

目录

  • [0.x]前言
  • [1.x]线性dp
  • [2.x]背包
  • [3.x]区间dp
  • [4.x]树形dp★
  • [5.x]环形与后效性处理
  • [6.x]状压dp
  • [7.x]倍增优化dp
  • [8.x]数据结构优化dp
  • [9.x]单调队列优化dp

[1.x]线性dp

[1.1]最长上升序列(LIS)问题

模型描述：给定序列A，求数值单调递增的子序列的长度最长为多少。

例题：luogu P1020 导弹拦截（最长不上升序列+最长上升序列）

例题分析：

容易分析得到，第一问是求最长不上升序列，第二问求最长上升序列。板子题。

以最长上升序列为例子。

思路如下：

我们维护一个有序数列[算法] 动规专题 - 图2，用来储存一个上升序列，注意，这里的升序需要我们手动维护，不可以通过STL自动排序，否则会失去意义。

1-从首位开始扫描
2.1-当有[算法] 动规专题 - 图3时，执行[算法] 动规专题 - 图4将[算法] 动规专题 - 图5入列。
2.2-当有[算法] 动规专题 - 图6时，执行[算法] 动规专题 - 图7-(d%2B1)%5D%20%3D%20a%5Bi%5D#card=math&code=d%5Blower%5C_bound%28d%2B1%2Cd%2Btail%2B1%2Ca%5Bi%5D%29-%28d%2B1%29%5D%20%3D%20a%5Bi%5D&id=Ep3s0)将[算法] 动规专题 - 图8覆盖[算法] 动规专题 - 图9中[算法] 动规专题 - 图10的最小整数。合理理由如下:

  • 覆盖以后依然满足升序
  • 覆盖后的序列与原序列相比条件更大，更容易匹配更长的序列，满足子问题最优性
  • 对于之后的元素，如果能跟入之前的序列，那必定也能跟入当前序列，满足无后效性
    3-扫描结束，[算法] 动规专题 - 图11即序列长度即为最长序列，但[算法] 动规专题 - 图12中存储的并不一定是答案的最长序列

代码样例：

  1. int d[100],len = 1;
  2. void LIS(){
  3.     len = 1;
  4.     d[1] = a[1];
  5.     for(int i = 2;i <= n;i++){
  6.         if(a[i] > d[len]) d[++len] = a[i];
  7.         else if(a[i] <= d[len]){
  8.             int pos = lower_bound(d+1,d+len+1,a[i]) - (d+1) + 1;
  9.             d[pos] = a[i];
  10.         }
  11.     }
  12.     cout << len << endl;
  13. }
  14. //maybe出锅?

第一小问求的是最长不上升序列，可以类比。

维护一个降序序列，但是这样的话upper_bound/lower_bound就不可以直接用了，需要再传一个比较规则greater<int>()。

然后覆盖队列的条件也需要改，因为是不上升，用lower_bound会丢失答案，所以元素小于等于队尾都可以加入队尾，否则应该找一个大于它的来覆盖，即用upper_bound。

AC代码：

{% spoiler “Code” %}

  1. //luogu P1020 导弹拦截
  2. #include<iostream>
  3. #include<cstring>
  4. #include<cstdio>
  5. #include<algorithm>
  6. using std::cin;using std::cout;using std::endl;
  7. typedef long long ll;
  8. typedef unsigned long long ull;
  9. using std::upper_bound;using std::lower_bound;
  10. int a[100005],d1[100005],d2[100005],x,len1 = 1,len2 = 1,n;
  11. int main(){
  12.       while(cin>>a[++n]){
  13.           if(n == 1){d1[1] = a[1] , d2[1] = a[1] ; continue;}
  14.           else{
  15.               if(d1[len1] < a[n]){
  16.                   int p = upper_bound(d1+1,d1+len1+1,a[n],std::greater<int>()) - d1;
  17.                   d1[p] = a[n];
  18.               }else d1[++len1] = a[n];
  19.             if(d2[len2] >= a[n]){
  20.                 int p = lower_bound(d2+1,d2+len2+1,a[n]) - d2;
  21.                 d2[p] = a[n];
  22.             }else d2[++len2] = a[n];
  23.           }
  24.       }
  25.     cout << len1 << endl << len2;
  26.     return 0;
  27. }

{% endspoiler %}

[1.2]最长公共子序列LCS

虽然luogu有模板题但是luoguLCS模板的数据要求用LIS做就很艹(所以没法贴

思路如下：

很正常的[算法] 动规专题 - 图13，[算法] 动规专题 - 图14表示[算法] 动规专题 - 图15和[算法] 动规专题 - 图16的最大[算法] 动规专题 - 图17，有转移方程：

[算法] 动规专题 - 图18%0A%5Cend%7Bmatrix%7D%5Cright.%0A#card=math&code=dp%5Bi%5D%5Bj%5D%20%3D%20max%0A%5Cleft%5C%7B%5Cbegin%7Bmatrix%7D%0Adp%5Bi-1%5D%5Bj%5D%20%26%5C%5C%20%0Adp%5Bi%5D%5Bj-1%5D%20%26%5C%5C%20%0Adp%5Bi-1%5D%5Bj-1%5D%2B1%20%26%20%E5%BD%93%E4%B8%94%E4%BB%85%E5%BD%93%28a%5Bi%5D%20%3D%3D%20b%5Bj%5D%29%0A%5Cend%7Bmatrix%7D%5Cright.%0A&id=eRq9e)

代码样例：

  1. void LCS(){
  2.     for(int i = 1;i <= n;i++){
  3.         for(int j = 1;j <= n;j++){
  4.             dp[i][j] = dp[i-1][j] > dp[i][j-1] ? dp[i-1][j] : dp[i][j-1];
  5.             if(a[i] == b[j]){
  6.                 dp[i][j] = dp[i][j] > dp[i-1][j-1]+1 ? dp[i][j] : dp[i-1][j-1]+1;
  7.             }
  8.         }
  9.     }
  10.     cout << dp[n][n];
  11. }

[1.3]相关题目

P1439 【模板】最长公共子序列

CodeForces 10D

P1216 [IOI1994][USACO1.5]数字三角形 Number Triangles

[2.x]背包

[2.1]01背包

模型描述：[算法] 动规专题 - 图19件物品，第[算法] 动规专题 - 图20件物品的体积为[算法] 动规专题 - 图21，价值为[算法] 动规专题 - 图22。有一个容积为[算法] 动规专题 - 图23的背包，要求选择一些物品放入背包，使得物品总体积不超过[算法] 动规专题 - 图24的前提下物品的价值的和最大。（每个物品只有一个）

思路：

把背包分为[算法] 动规专题 - 图25种小背包，[算法] 动规专题 - 图26表示放入体积[算法] 动规专题 - 图27时最大价值为多少。有转移方程：

[算法] 动规专题 - 图28

容易得到如下性质：

  • [算法] 动规专题 - 图29从[算法] 动规专题 - 图30扫描时（小到大），可能会调用刚刚更新过的背包，这就导致同一物品拿了多次，对应完全背包。
  • [算法] 动规专题 - 图31从[算法] 动规专题 - 图32扫描时（大到小），必定不会调用到刚刚更新过的背包，即每个物品只会拿一次，对应01背包。

样例代码：

  1. 读入;
  2. dp[0] = 0;
  3. for(int i = 1;i <= N;i++){
  4.     for(int j = M;j >= V[i];j--){
  5.         dp[j] = dp[j] > dp[j-V[i]] + W[i] ? dp[j] : dp[j-V[i]] + W[i];
  6.     }
  7. }
  8. int ans = 0;
  9. for(int i = 1;i <= M;i++) ans = ans > dp[i] ? ans : dp[i];
  10. 输出;

[2.2]完全背包

模型描述：[算法] 动规专题 - 图33件物品，第[算法] 动规专题 - 图34件物品的体积为[算法] 动规专题 - 图35，价值为[算法] 动规专题 - 图36。有一个容积为[算法] 动规专题 - 图37的背包，要求选择若干件物品放入背包，使得物品总体积不超过[算法] 动规专题 - 图38的前提下物品的价值的和最大。（每个物品有无穷多个）

过程雷同01背包，更改顺序，理由见上。

  1. 读入;
  2. dp[0] = 0;
  3. for(int i = 1;i <= N;i++){
  4.     for(int j = V[i];j <= M;j++){
  5.         dp[j] = dp[j] > dp[j-V[i]] + W[i] ? dp[j] : dp[j-V[i]] + W[i];
  6.     }
  7. }
  8. int ans = 0;
  9. for(int i = 1;i <= M;i++) ans = ans > dp[i] ? ans : dp[i];
  10. 输出;

[2.3]多重背包

模型描述：[算法] 动规专题 - 图39件物品，第[算法] 动规专题 - 图40件物品的体积为[算法] 动规专题 - 图41，价值为[算法] 动规专题 - 图42，且有[算法] 动规专题 - 图43个。有一个容积为[算法] 动规专题 - 图44的背包，要求选择若干件物品放入背包，使得物品总体积不超过[算法] 动规专题 - 图45的前提下物品的价值的和最大。（每个物品有限多个）

思路：把[算法] 动规专题 - 图46件物品当做不同的物品。朴素可做，二进制拆分和单调队列可优化。

暂咕

[2.4]分组背包

模型描述：给定[算法] 动规专题 - 图47组物品，其中第[算法] 动规专题 - 图48组有[算法] 动规专题 - 图49个物品。第[算法] 动规专题 - 图50组的第[算法] 动规专题 - 图51个物品的体积为[算法] 动规专题 - 图52价值为[算法] 动规专题 - 图53。有一个容积为[算法] 动规专题 - 图54的背包，要求选择若干个物品放入背包，使得每组至多选择一个物品并且物品总体积不超过[算法] 动规专题 - 图55的前提，物品的价值总和最大。

思路：[算法] 动规专题 - 图56处理体积为[算法] 动规专题 - 图57的背包。与01背包不同的是，这次01的对象被分组了，但并不影响做题过程。我们只需要一个组一个组的做就行了，但是需要注意，枚举组内对象的循环必须放在枚举背包空间的内部，这是为了维护每组只能选择一个的条件。

样例代码：

  1. 输入;
  2. for(int i = 1;i <= N;i++){//枚举组
  3.     for(int j = M;j >= 0;j--){//枚举空间
  4.         for(int k = 1;k <= C[i];k++){//枚举组内物品
  5.             if(j-V[k] < 0) continue;//防炸
  6.             dp[j] = dp[j] > dp[j-V[i][k]] + W[i][k] ? dp[j] : dp[j-V[i][k]] + W[i][k];
  7.         }
  8.     }
  9. }
  10. int ans = 0;
  11. for(int i = 1;i <= M;i++) ans = ans > dp[i] ? ans : dp[i];
  12. 输出;

[2.5]相关题目

采药

疯狂的采药

P1757 通天之分组背包

P1064 金明的预算方案（数据弱化的背包树形dp，可以用分类讨论+01背包过）

[3.x]区间dp

区间dp的思想是维护[算法] 动规专题 - 图58，表示区间[算法] 动规专题 - 图59内的最优解。

一般以区间长为阶段。

[2.1]相关题目

P1880 [NOI1995]石子合并

P1063 能量项链

P1220 关路灯

P3205 [HNOI2010]合唱队

[4.x]树形dp★

[4.1]正常树形dp

树形dp一般以节点深度作为阶段，第一维通常记录临时根节点的编号。一般利用递归来进行规划，回溯时进行转移。

P1352 没有上司的舞会

[4.2]背包类树形dp

P1272 重建道路

可以参考这里

[4.3]二次扫描与换根法

咕咕咕，没脑子看不懂暂时咕了

[6.x]状压dp

所谓状压[算法] 动规专题 - 图60，就是将[算法] 动规专题 - 图61状态压缩到二进制中表示，例如在图论中，用二进制第[算法] 动规专题 - 图62位的[算法] 动规专题 - 图63来表示是否到过第[算法] 动规专题 - 图64过点。

  • 具体的：0010 0011 表示该图中已经走过第[算法] 动规专题 - 图65号点。
  • 类似的，我们可以用10进制来表示一组特定序列的阿拉伯数字串：
    • 1314可以用来表示一个[算法] 动规专题 - 图66的方阵的[算法] 动规专题 - 图67值[算法] 动规专题 - 图68#card=math&code=%28%5E%7B1%E3%80%803%7D_%7B1%E3%80%804%7D%29&id=a33nz)
  • 而用二进制表示状态可以用最小的数据量表示最大的信息规模，是[算法] 动规专题 - 图69进制存[算法] 动规专题 - 图70的变种

这么做以后，我们可以把一整张图的信息状态存在一个整数里，这样，我们可以直接将它作为[算法] 动规专题 - 图71的下标进行[算法] 动规专题 - 图72。

不过状态压缩不一定是[算法] 动规专题 - 图73，状态压缩同样可以用在别的地方，比如标记这条路径是否可行等。

注意到求路径可能出现小数点，所以用[算法] 动规专题 - 图74存长度。

观察[算法] 动规专题 - 图75，猜测使用状压，猜测状压表示已经走过的点。

  • 构造求距离函数dis()
  • 由小规模状态开始枚举，推导得到后一种状态
    • 枚举过程中：先找到作为当前点的[算法] 动规专题 - 图76，再枚举作为下一个点的[算法] 动规专题 - 图77

转移方程：

[算法] 动规专题 - 图78)%0A#card=math&code=dp%7Bnow%20%7C%20j%2Cj%7D%20%3D%20min%28dp%7Bnow%20%7C%20j%2Cj%7D%2Cdp_%7Bnow%2Ci%7D%2Bdis%28i%2Cj%29%29%0A&id=KW5cm)

其中[算法] 动规专题 - 图79为枚举的局面，[算法] 动规专题 - 图80为我从中选出的“当前点”，[算法] 动规专题 - 图81为我枚举出的下一个点，[算法] 动规专题 - 图82#card=math&code=dis%28i%2Cj%29&id=OCWU9)为两点距离

{% spoiler “Code” %}

  1. #include<iostream>
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<cmath>
  6. #include<map>
  7. #include<set>
  8. #include<vector>
  9. #include<queue>
  10. #include<cstdlib>//rand()
  11. #define rep(i,a,b) for(register int i = (a);i <= (b);++i)
  12. #define per(i,a,b) for(register int i = (a);i >= (b);--i)
  13. typedef long long ll;
  14. typedef unsigned long long ull;
  15. using std::string;using std::cin;using std::cout;
  17. int n;
  18. double dp[40000][20],inf = 1e9+9;
  19. struct node{double x,y;}a[20];
  21. inline double min(double x,double y){if(x < y) return x; else return y;}
  22. inline double dis(double x1,double y1,double x2,double y2){return std::sqrt((x1-x2)*(x1-x2)+(y1-y2)*(y1-y2));}
  23. int main(){
  24.     std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  25.     //freopen("in.in", "r", stdin);
  26.     cin >> n;
  27.     rep(i,1,n) cin >> a[i].x >> a[i].y;
  28.     rep(i,0,(1 << n)) rep(j,0,n+1) dp[i][j] = inf;
  29.     rep(i,1,n) dp[ 1 << (i - 1) ][i] = dis(0,0,a[i].x,a[i].y);
  30.     rep(now,1,(1 << n) - 1){
  31.         rep(i,1,n){
  32.             if(now & (1<<(i-1)) == 0) continue;
  33.             rep(j,1,n){
  34.                 if(now & (1<<(j-1)) == 1) continue;
  35.                 dp[now | (1<<(j-1))][j] = std::min(dp[now][i]+dis(a[i].x,a[i].y,a[j].x,a[j].y) , dp[now | (1<<(j-1))][j]);
  36.             }
  37.         }
  38.     }
  39.     double ans = inf;
  40.     rep(i,1,n) ans = min(ans,dp[(1 << n) - 1][i]);
  41.     printf("%.2lf\n",ans);
  42.     return 0;
  43. }

{% endspoiler %}

同样，观察到[算法] 动规专题 - 图83，猜测用二进制压缩选了人的情况

对于每一个局面，具有的属性有：ww[now]：表示局面now下总载重；tt[now]：表示局面now下最大用时

所求dp[now]：表示局面now下最小用时

那么，我们先枚举计算得到ww[now]和tt[now]，然后再用它们来做[算法] 动规专题 - 图84

转移方程：

[算法] 动规专题 - 图85%0A#card=math&code=dpi%20%3D%20min%28dp_i%2Ctt_j%2Bdp%7Bi%5Coplus%20j%7D%29%0A&id=uAEKN)

其中[算法] 动规专题 - 图86为当前计算的局面，[算法] 动规专题 - 图87为我所枚举的转移状态，也就是说我的[算法] 动规专题 - 图88是由局面[算法] 动规专题 - 图89和[算法] 动规专题 - 图90合并而来的。

{% spoiler “Code” %}

  1. #include<iostream>
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<cmath>
  6. #include<map>
  7. #include<set>
  8. #include<vector>
  9. #include<queue>
  10. #include<cstdlib>//rand()
  11. #define rep(i,a,b) for(register int i = (a);i <= (b);++i)
  12. #define per(i,a,b) for(register int i = (a);i >= (b);--i)
  13. typedef long long ll;
  14. typedef unsigned long long ull;
  15. using std::string;using std::cin;using std::cout;
  17. const int inf = 1e9+9;
  18. int W,n,t[20],w[20],ans,dp[1<<17],tt[1<<17],ww[1<<17];
  20. int main(){
  21.     std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  22.     //freopen("in.in", "r", stdin);
  23.     cin >> W >> n;
  24.     rep(i,1,n) cin >> t[i] >> w[i];
  25.     rep(i,0,(1<<n)-1){
  26.         dp[i] = inf;
  27.         rep(j,1,n){
  28.             if(i & (1<<(j-1))) continue;
  29.             tt[i | (1<<(j-1))] = std::max(tt[i],t[j]);
  30.             ww[i | (1<<(j-1))] = ww[i] + w[j];
  31.         }
  32.     }
  33.     dp[0] = 0;
  34.     rep(i,1,(1<<n)-1)
  35.         for(int j = i;j;j = (j-1) & i)
  36.             if(ww[j] <= W) dp[i] = std::min(dp[i],dp[i ^ j] + tt[j]);
  37.     cout << dp[(1<<n)-1] << "\n";
  38.     return 0;
  39. }

{% endspoiler %}

做的时间有点久远，等我回过头复习

{% spoiler “Code” %}

  1. #include<iostream>
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. //int[1e7] ll[5*1e6]
  6. typedef long long ll;
  7. typedef unsigned long long ull;
  8. using std::cin;using std::cout;using std::endl;
  10. int dp[14][1 << 13],n,m,p,mod = 1000000000;
  11. int map[14],flag[1 << 13];
  13. int main(){
  15.     cin >> n >> m;
  16.     for(register int i = 1;i <= n;++i){
  17.         for(register int j = 1;j <= m;++j){
  18.             cin >> p;
  19.             map[i] = (map[i] << 1) + p;
  20.         }
  21.     }
  24.     for(register int i = 0;i < (1 << m);++i){
  25.         if((!(i & (i >> 1))) && (!(i & (i << 1)))) flag[i] = 1;
  26.         if((i & map[1]) == i && flag[i]) dp[1][i] = 1;
  27.         // cout << dp[1][i] << " ";
  28.     }
  30.     for(register int i = 2;i <= n;++i){
  31.         // cout << 1 << "\n";
  32.         for(register int j = 0;j < (1 << m);++j){
  33.             // cout << 2 << "\n";
  34.             if(((map[i-1] & j) == j) && flag[j]){
  35.                 for(register int k = 0;k < (1 << m);++k){
  36.                     if(((map[i] & k) == k) && flag[k] && !(k & j)){
  37.                         dp[i][k] += dp[i-1][j];
  38.                         dp[i][k] %= mod;
  39.                         // cout << "dp[i][k] = " << dp[i][k] << "\n";
  40.                     }
  41.                 }
  42.             }
  43.         }
  44.     }
  45.     int ans = 0;
  46.     for(register int i = 0;i < (1 << m);++i){
  47.         ans += dp[n][i];
  48.         ans %= mod;
  49.     }
  50.     cout << ans;
  51.     return 0;
  52. }

{% endspoiler %}

老样子，看到这个十几的数字就知道该状压了，并且这次是[算法] 动规专题 - 图91，那么很显然这里需要记录的是[算法] 动规专题 - 图92种宝玉的状态

提取关键词：有向图，最短，点数为 [算法] 动规专题 - 图93 、恰好经过全部 [算法] 动规专题 - 图94 种颜色的路径

那么我们可以得到以下性质：我们每一次向下走的时候，不走颜色相同的，且路径有向。

所以大概解法就是：

  • 1.枚举起点
  • 2.[算法] 动规专题 - 图95向下搜索，记得剪枝

这里的[算法] 动规专题 - 图96其实是用来剪枝的(大概)，即记忆化，这样方便找到当某一条路比之前还要劣的时候可以及时返回。

{% spoiler “Code” %}

  1. #include<iostream>
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<cmath>
  6. #include<map>
  7. #include<set>
  8. #include<vector>
  9. #include<queue>
  10. #include<cstdlib>//rand()
  11. #define rep(i,a,b) for(register int i = (a);i <= (b);++i)
  12. #define per(i,a,b) for(register int i = (a);i >= (b);--i)
  13. typedef long long ll;
  14. typedef unsigned long long ull;
  15. using std::string;using std::cin;using std::cout;
  17. int n,m,k,a[111],u,v,w,map[111][111],dp[(1<<14)][111],ans;
  18. const int inf = 2e9+9;
  20. inline void dfs(int p,int now,int sum){
  21.     if(sum >= ans || now & (1<<a[p]) || dp[now][p] <= sum) return;
  22.     //当前答案比已有答案劣，返回
  23.     //当前点颜色已经被选过，返回
  24.     //当前路径已经有更优的解法，返回
  25.     if((now | (1<<a[p])) == (1<<k) - 1){
  26.         ans = std::min(ans,sum);
  27.         return;
  28.     }
  29.     dp[now][p] = sum;
  30.     rep(i,1,n) if(map[p][i] != inf) dfs(i,now | (1<<a[p]),sum + map[p][i]);
  31.     return;
  32. }
  34. int main(){
  35.     std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  36.     //freopen("in.in", "r", stdin);
  37.     cin >> n >> m >> k;
  38.     ans = inf;
  39.     rep(i,1,n) cin >> a[i];
  40.     rep(i,0,(1<<k)-1) rep(j,0,n) dp[i][j] = inf;
  41.     rep(i,0,n) rep(j,0,n) map[i][j] = inf; 
  42.     rep(i,1,m){
  43.         cin >> u >> v >> w;
  44.         map[u][v] = w;//有向边
  45.     }
  46.     rep(i,1,n) dp[ 1<<a[i] ][i] = 0;//选起点
  47.     ans = inf;
  48.     rep(i,1,n) dfs(i,0,0);
  49.     if(ans == inf) cout << "Ushio!\n";
  50.     else cout << ans << "\n";
  51.     return 0;
  52. }

{% endspoiler %}

枚举起点，初始化，开始搜索，压缩当前已经到了的点的状态，记录深度，更新答案

{% spoiler “Code” %}

  1. #include<iostream>
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<cmath>
  6. #include<map>
  7. #include<set>
  8. #include<vector>
  9. #include<queue>
  10. #include<cstdlib>//rand()
  11. #define rep(i,a,b) for(register long long i = (a);i <= (b);++i)
  12. #define per(i,a,b) for(register long long i = (a);i >= (b);--i)
  13. typedef long long ll;
  14. typedef unsigned long long ull;
  15. using std::string;using std::cin;using std::cout;
  17. int ans,n,m,dp[10000],a[15][15],u,v,w,dis[15],tmp;
  18. int inf = 1e9+9;
  20. inline void solve(int now){
  21.     rep(i,1,n){
  22.         if(((1 << (i-1)) & now) == 0) continue;
  23.         rep(j,1,n){
  24.             if(((1 << (j-1)) & now) == 0 && a[i][j] != inf){
  25.                 int nnow = now | (1 << (j-1));
  26.                 if(dp[ nnow ] > dp[now] + dis[i] * a[i][j]){
  27.                     tmp = dis[j] , dis[j] = dis[i] , ++dis[j];
  28.                     dp[ nnow ] = dp[now] + dis[i] * a[i][j];
  29.                     solve(nnow);
  30.                     dis[j] = tmp;
  31.                 }
  32.             }
  33.         }
  34.     }
  35. }
  37. int main(){
  38.     std::ios::sync_with_stdio(0);cin.tie(0);cout.tie(0);
  39.     //freopen("in.in", "r", stdin);
  40.     cin >> n >> m;
  42.     ans = inf;
  43.     rep(i,1,n) rep(j,1,n) a[i][j] = inf;    
  44.     rep(i,1,m){
  45.         cin >> u >> v >> w;
  46.         a[u][v] = std::min(a[u][v],w);
  47.         a[v][u] = std::min(a[v][u],w);
  48.     }
  49.     rep(i,1,n){
  50.         rep(i,1,n) dis[i] = inf;
  51.         rep(i,0,(1 << n) - 1) dp[i] = inf;
  52.         dis[i] = 1;
  53.         dp[1 << (i-1)] = 0;
  54.         solve(1 << (i-1));
  55.         ans = std::min(ans,dp[(1 << n)-1]);
  56.     }
  57.     cout << ans << "\n";
  58.     return 0;
  59. }

{% endspoiler %}

[9.x]单调队列优化dp

我们知道，dp的转移方程有时候会出现类似 [算法] 动规专题 - 图97%2Ck%5Cin%20%EF%BC%9F#card=math&code=max%28dp%5Bi-1%5D%5Bk%5D%29%2Ck%5Cin%20%EF%BC%9F&id=GsF42) 的情况，这时候当 [算法] 动规专题 - 图98 的可取范围过大时，就会出问题。

区间求最值，常见有 线段树/树状数组、ST表、单调队列。前几个由于实现过于复杂，所以我们一般使用单调队列来优化。

关于单调队列的相关内容，请看这里(2.1)

  • 例题：

P5858 「SWTR-03」Golden Sword

(最小值一开始选了-1e9然后WA了无数次……)

  • dp维护放置第i物品，锅内(包括将要放入的)有j物品的最大耐久
    • 转移方程：[算法] 动规专题 - 图99%20%2B%20j%20*%20a%5Bi%5D%2Ck%5Cin%5Bj-1%2Cj%2Bs-1%5D#card=math&code=dp%5Bi%5D%5Bj%5D%20%3D%20max%28dp%5Bi-1%5D%5Bk%5D%29%20%2B%20j%20%2A%20a%5Bi%5D%2Ck%5Cin%5Bj-1%2Cj%2Bs-1%5D&id=XWFf5)
  • 单调队列维护 [算法] 动规专题 - 图100%2Ck%5Cin%5Bj-1%2Cj%2Bs-1%5D#card=math&code=max%28dp%5Bi-1%5D%5Bk%5D%29%2Ck%5Cin%5Bj-1%2Cj%2Bs-1%5D&id=b3ji3)
    • [算法] 动规专题 - 图101 需要维护 [算法] 动规专题 - 图102 的范围，[算法] 动规专题 - 图103 来维护单调性

{% spoiler “Code” %}

  1. #include<iostream>
  2. #include<cstring>
  3. #include<cstdio>
  4. #include<algorithm>
  5. #include<cmath>
  6. #include<map>
  7. #include<set>
  8. #include<queue>
  9. #include<cstdlib>//rand()
  10. #define rep(i,a,b) for(register long long i = (a);i <= (b);++i)
  11. #define per(i,a,b) for(register long long i = (a);i >= (b);--i)
  12. typedef long long ll;
  13. typedef unsigned long long ull;
  14. using std::string;using std::cin;using std::cout;
  15. ll n,w,s,dp[5505][5505],q[5555],p[5555],a[5555],l,r,ans;
  16. int main(){
  17.     cin >> n >> w >> s;
  18.     rep(i,1,n) cin >> a[i];
  19.     rep(i,0,n+1) rep(j,0,w+1) dp[i][j] = -1e16;
  20.     dp[1][1] = a[1];
  21.     rep(i,2,n){
  22.         l = r = 1 , q[l] = dp[i-1][w] , p[l] = w;
  23.         per(j,w,1){
  24.             while(!(p[l] <= j+s-1 && p[l] >= j-1) && l <= r) ++l;
  25.             while(!(q[r] >= dp[i-1][j-1]) && l <= r) --r;
  26.             q[++r] = dp[i-1][j-1] , p[r] = j - 1;
  27.             dp[i][j] = q[l] + j * a[i];
  28.         }
  29.     }
  30.     ans = -1e16;
  31.     rep(i,1,w) ans = std::max(ans,dp[n][i]);
  32.     cout << ans << "\n";
  33.     return 0;
  34. }

{% endspoiler %}