记忆化搜索

  • 记忆化搜索不依赖于任何外部变量（外部变量即指定义于dfs函数外且值随dfs运行而改变的变量）
  • 答案以返回值的形式存在，而不能以参数的形式存在
  • 对于同一组参数，dfs的返回值是相同的

背包问题&单调队列优化

引例 C. Watching Fireworks is Fun

设fi,jf_{i,j}表示在放第i个烟花时，在位置j能获得最大的快乐值

状态转移方程 fi,j=max{fi−1,k+bi−∣ai−j∣}f_{i,j}=max \{ f_{i-1,k} +b_i-\lvert a_i-j \rvert \}

注意这里的k是有范围的 j−(ti−ti−1)×d≤k≤(ti−ti−1)×dj-(t_i-t_{i-1})\times d\le k \le (t_i-t_{i-1}) \times d

最终式子化为 fi,j=max{fi−1,k−∣ai−j∣}+bi=max{fi−1,k}−∣ai−j∣+bif_{i,j}=max \{f_{i-1,k}- \lvert a_i-j \rvert \} +b_i=max \{f_{i-1,k} \} - \lvert a_i-j \rvert +b_i

本题中，维护一个单调队列，在加入新的元素的时候，如果前面的元素比它的值小，则弹出前面的元素，直到遇到比它大的才停止，即最后的队列是单调递减的

注意最左边的元素有可能越界了，这时候也要弹出

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
#include <algorithm>
#include <cstring>
#include <iostream>
using namespace std;
typedef long long ll;

const int maxn = 150000 + 10;
const int maxm = 300 + 10;

ll f[2][maxn];
ll a[maxm], b[maxm], t[maxm];
int n, m, d;

int que[maxn];

int fl = 1;
void init() {
  memset(f, 207, sizeof(f));
  memset(que, 0, sizeof(que));
  for (int i = 1; i <= n; i++) f[0][i] = 0;
  fl = 1;
}

void dp() {
  init();
  for (int i = 1; i <= m; i++) {
    int l = 1, r = 0, k = 1;
    for (int j = 1; j <= n; j++) {
      for (; k <= min(1ll * n, j + d * (t[i] - t[i - 1])); k++) {
        while (l <= r && f[fl ^ 1][que[r]] <= f[fl ^ 1][k]) r--;
        que[++r] = k;
      }

      while (l <= r && que[l] < max(1ll, j - d * (t[i] - t[i - 1]))) l++;
      f[fl][j] = f[fl ^ 1][que[l]] - abs(a[i] - j) + b[i];
    }

    fl ^= 1;
  }
}

int main() {
  cin >> n >> m >> d;
  for (int i = 1; i <= m; i++) cin >> a[i] >> b[i] >> t[i];

  // then dp
  dp();
  ll ans = -1e18;
  for (int i = 1; i <= n; i++) ans = max(ans, f[fl ^ 1][i]);
  cout << ans << endl;
  return 0;
}

单调队列优化多重背包

问题描述

你有n个物品，每个物品重量为wiw_i，价值为viv_i，数量为kik_i。你有一个承重上限为m的背包，现在要求你在不超过重量上限的情况下选取价值和尽可能大的物品放入背包。求最大价值。

常规做法

容易想到可以把第i种物品通过二进制拆分，大致拆成log⁡(ki)\log(k_i)个独立的物品，注意要保证能用这些拆分后的独立的物品组合成在11~kik_i中任意的数量，并且全部选完后不能超过kik_i

单调队列优化

还有一种方法是使用单调队列优化，这样的复杂度是最优的，相比于二进制拆分少了log的复杂度

该部分参考了一篇博客，在这里补充一下我的理解

使用单调队列优化时，大致的思路还是没有变。用f[i][j]f[i][j]表示购买前i种物品并且占用了空间j时，能得到的最大的价值。外面的第一层循环仍然是循环物品的种类，即用f[i−1][]f[i-1][ ]来更新f[i][]f[i][ ]。由于我们只需要用到i-1，所以可以把f数组第一项消除即将其变成一维

在第i层循环中，只能购买第i种物品，设第i中物品的体积是viv_i。若此时要更新f[j]f[j]（设j/vi=mj/v_i=m，且余数为j%vij \% v_i）的值，则只能从下标为j%vi,j%vi+vi,j%vi+2×vi,...,j%vi+m×vij \% v_i,j \%v_i+v_i,j \% v_i+2 \times v_i,...,j\% v_i+m \times v_i的项得到

所以我们第二层循环为余数，即从00到vi−1v_i-1。然后第三层循环可以理解为枚举体积j%vi,j%vi+vi,j%vi+2×vi,...,j%vi+m×vij \% v_i,j \%v_i+v_i,j \% v_i+2 \times v_i,...,j\% v_i+m \times v_i。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
for(int i=1;i<=n;i++)//枚举物品种类 
{
	cin>>c[i]>>w[i]>>num[i];//c,w,num分别对应 体积,价值,个数 
	if(V/c[i]<num[i]) num[i]=V/c[i];//求lim
	for(int mo=0;mo<c[i];mo++)//枚举余数 
	{
		head=tail=0;//队列初始化 
		for(int k=0;k<=(V-mo)/c[i];k++) //枚举总体积k*c[i]+mo
		{
			int x=k;
			int y=f[k*c[i]+mo]-k*w[i];
			while(head<tail && que[head].pos<k-num[i])head++;
			//因为最多只能买num[i]件物品i，所以不能从体积为que[head].pos的情况更新f[k*c[i]+mo]
			while(head<tail && que[tail-1].value<=y)tail--;
			//保证队列单调递减的
			que[tail].value=y,que[tail].pos=x;
			tail++;
			f[k*c[i]+mo]=que[head].value+k*w[i];
            //加上k*w[i]的原因:
            //由于前面定义入队时是y，即y=f[k*c[i]+mo]-k*w[i];这里减去了一个当时的k*w[i]，然后现在再加上此时的k*w[i]，两个k的差就是购买的第i件物品的数量
		}
	}
}

习题

滑动窗口

单调队列的板子题

「NOI2005」瑰丽华尔兹

容易想到可以用f(time,x,y)来定义在time时刻，位于(x,y)处走过的最长路径，但是这样的复杂T∗M∗NT*M*N，显然超时。注意到一个时间段内只能向着一个方向移动，对于同一行或列可以只用考虑相对位置。得到f[j]=max{f[i]+j−i},i<jf[j]=max\{ f[i]+j-i\},i<j，即f[j]−j=max{f[i]−i}f[j]-j=max\{ f[i]-i\}。可以想到使用单调队列存储各个f[i]−if[i]-i的值，从而降低复杂度

其实我们可以发现，像这样的通过求某一个区间的极值来更新后续状态的情况，都可以用单调队列来求解

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;

const int INF = 0x3f3f3f3f;
const int MAXN = 205;
const int dx[] = {0,0,0,-1,1};
const int dy[] = {0,-1,1,0,0};

int n,m,ans,sx,sy,k;
char mp[MAXN][MAXN];
int f[MAXN][MAXN];

struct Period{
	int bgn,end,dir;//每个时段的开始、结束时间及船的方向 
} p[MAXN];		// 记录各时间区间及方向的信息

struct Node{
	int pos,val;
};

deque<Node> q;

void caculate(int x,int y,int dir,int len){//起点、方向、时长窗口区间
	q.clear();
	int idx = 0;
        // idx : 相对于本区间开始位置的、本方向上的位移量
	while(x >= 1 && x <= m && y >= 1 && y <= n){
		if(mp[y][x] == 'x'){ //注意此处和下面的行号列号
		    q.clear();
		}else{
			while(!q.empty() && q.back().val <= f[y][x] - idx)
			    q.pop_back(); // 递减的单调队列
			q.push_back((Node){idx,f[y][x] - idx});
            		// j、pos 都是相对于起始位置的相对位置，一减即得到区间长度
			if(idx - q.front().pos > len) 
			    q.pop_front();// 把队首往后调整至落入当前时长的“窗口区间”内
			f[y][x] = q.front().val + idx;
			ans = max(ans,f[y][x]);
		}
		x += dx[dir];
		y += dy[dir];
		idx++;
        	//改变当前的位置和距离
	}
}

int main(){
	scanf("%d%d%d%d%d",&n,&m,&sx,&sy,&k);
	for(int i = 1;i <= n;i++){
		for(int j = 1;j <= m;j++){
		    cin >> mp[i][j];
		    f[i][j] = -100000;
		}
	}
	for(int i = 1;i <= k;i++)
	    scanf("%d%d%d",&p[i].bgn,&p[i].end,&p[i].dir);
	f[sx][sy] = 0;
	for(int i = 1;i <= k;i++){// 按时段来推
		int len = p[i].end - p[i].bgn + 1;// 当前时间区间的时长
		switch(p[i].dir){		  // 4 个方向
			case 1:
				for(int j = 1;j <= m;j++)
				    caculate(j,n,1,len); //上
				break;
			case 2:
				for(int j = 1;j <= m;j++)
				    caculate(j,1,2,len); //下
				break;
			case 3:
				for(int j = 1;j <= n;j++)
				    caculate(m,j,3,len); //左
				break;
			case 4:
				for(int j = 1;j <= n;j++)
				    caculate(1,j,4,len); //右
				break;
		}
	}
	printf("%d\n",ans);
	return 0;
}

「SCOI2010」股票交易

这道题的状态很好定义，即用f[i][j]f[i][j]表示在第i天持有j个股票时赚到的钱的最大值（注意这里赚到的钱可能是负数）。然后我们需要挖掘一下隐藏的信息，这也是这道题的难点

  • 首先，如果我们第i天不进行任何操作，则可以得到f[i][j]=max(f[i][j],f[i−1][j])f[i][j]=max(f[i][j],f[i-1][j])
  • 第i天如果执行买入或者卖出的操作，我们只需要考虑第i-W-1天的状态来更新第i天的状态。

为什么考虑第i-W-1天的状态即可？
如果能用第i-w天到第i-1天之间某一天（记为k）的状态来更新第i天的状态，说明第k天没有进行任何操作，则第k天的状态与第k-1的状态一样。依此类推，我们只需要考虑第i-W-1天的状态。
那么i-W-1天之前的天数需要考虑吗？显然可知对于相同的j（股票数），f[i][j]≥f[i−k][j](1≤k≤i)f[i][j]\ge f[i-k][j](1\le k\le i)，所以这些天的状态也不用考虑。
综上，只需要考虑第i-W-1天的状态来更新第i天

  • 根据前面的分析，我们可以写出递推式。
    买入：f[i][j]=max{f[i][j],max{f[i−w−1][k]−ap[i]∗(j−k)}}f[i][j]=max\{ f[i][j],max\{ f[i-w-1][k]-ap[i]*(j-k)\} \}
    卖出：f[i][j]=max{f[i][j],max{f[i−w−1][k]+bp[i]∗(k−j)}}f[i][j]=max\{ f[i][j],max\{ f[i-w-1][k]+bp[i]*(k-j)\} \}

分析完毕。这时如果变换一下递推式，得到（以买入时为例）：
f[i][j]=max{f[i][j],max{f[i−w−1][k]+ap[i]∗k}−ap[i]∗j}f[i][j]=max\{ f[i][j],max\{ f[i-w-1][k]+ap[i]*k\} -ap[i]*j\}

显然可以使用单调队列进行优化

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int N=2e3+5;
const ll inf=1ll<<62;
ll dp[N][N];
int T,maxP,W;
int ap[N],bp[N],as[N],bs[N];
struct node
{
    ll val;
    int pos;
}q[N];
int l,r;
int main()
{
    scanf("%d%d%d",&T,&maxP,&W);
    for(int i=1;i<=T;++i)
    scanf("%d%d%d%d",&ap[i],&bp[i],&as[i],&bs[i]);
    for(int i=0;i<=T;++i)
    for(int j=0;j<=maxP;++j)
   		dp[i][j]=-inf;
    for(int i=1;i<=T;++i)
    {
        for(int j=0;j<=as[i];++j)
        	dp[i][j]=-ap[i]*j;//假设前面的天数什么都没有买，然后第i天才买
        for(int j=0;j<=maxP;++j)
        	dp[i][j]=max(dp[i-1][j],dp[i][j]);
        int t=i-W-1;
        if(t>0){
			l=r=0;
			for(int j=0;j<=maxP;++j){
				while(l<r&&(j-q[l].pos)>as[i])l++;//
				while(l<r&&q[r-1].val<=dp[t][j]+1ll*j*ap[i])r--;
				q[r].pos=j;
				q[r++].val=dp[t][j]+1ll*j*ap[i];
				dp[i][j]=max(dp[i][j],q[l].val-1ll*j*ap[i]);
			}
			l=r=0;
			for(int j=maxP;j>=0;j--){
				while(l<r&&(q[l].pos-j)>bs[i])l++;
				while(l<r&&q[r-1].val<=dp[t][j]+1ll*j*bp[i])r--;
				q[r].pos=j;
				q[r++].val=dp[t][j]+1ll*j*bp[i];
				dp[i][j]=max(dp[i][j],q[l].val-1ll*j*bp[i]);
			}
        }
    }
    ll ans=-inf;
    for(int i=0;i<=maxP;++i)
    	ans=max(ans,dp[T][i]);
    printf("%lld\n",ans);
    return 0;
}

二维费用背包

「Luogu P1855」榨取 kkksc03

乍一看多了一个限制条件，其实这种题挺简单的，只需要多开一维数组，同时转移两个价值即可

1
2
3
4
5
for (int k = 1; k <= n; k++) {
  for (int i = m; i >= mi; i--)    // 对经费进行一层枚举
    for (int j = t; j >= ti; j--)  // 对时间进行一层枚举
      dp[i][j] = max(dp[i][j], dp[i - mi][j - ti] + 1);
}

分组背包

「Luogu P1757」通天之分组背包

第一层循环变量是不同的组，第二层是体积，第三层是该组的每一个元素。注意第二层循环要从大到小更新。

1
2
3
4
5
//伪代码
for 所有的组k
    for v=V..0
        for 所有的i属于组k
　　　　　　f[v]=max{f[v],f[v-w[i]]+c[i]}

有依赖的背包

「Luogu P1064」金明的预算方案

这种题目可以对于每一个不同的主件都建立一个树。然后对于这个树中的所有元素进行分析

对于包含一个主件和若干个附件的集合有以下可能性：仅选择主件，选择主件后再选择一个附件，选择主件后再选择两个附件……需要将以上可能性的容量和价值转换成一件件物品。因为这几种可能性只能选一种，所以可以将这看成分组背包。

如果是多叉树的集合，则要先算子节点的集合，最后算父节点的集合

泛化物品背包

这种背包，没有固定的费用和价值，它的价值是随着分配给它的费用而定。在背包容量为V的背包问题中，当分配给它的费用为viv_i时，能得到的价值就是h(vi)h(v_i)。这时，将固定的价值换成函数的引用即可。

特殊的背包问题

要求输出方案

定义一个新的变量gi,vg_{i,v}，表示第i件物品占用空间为v的时候是否选择了此物品。然后在转移时记录是选用了哪一种策略（选或不选）。输出时的伪代码：

1
2
3
4
5
6
7
8
int v = V;  // 记录当前的存储空间
for (从最后一件循环至第一件){ // 因为最后一件物品存储的是最终状态，所以从最后一件物品进行循环
  if (g[i][v]) {
    选了第 i 项物品;
    v -= 第 i 项物品的价值;
  } else
    未选第 i 项物品;
}

要求输出方案数

对于给定的一个背包容量、物品费用、其他关系等的问题，求装到一定容量的方案总数。

这种问题就是把求最大值换成求和即可

即dpi=∑(dpi,dpi−ci)dp_i=\sum{(dp_i,dp_{i-c_i})}

注意初始状态定义为dp0=1dp_0=1，因为什么都不装也是背包的一种方案

求最优方案总数

定义dp状态fi,jf_{i,j}为在只能放前i个物品的情况下，容量为j的背包正好装满所有的的最大总价值

这样修改之后，每一个dp状态都可以用gi,jg_{i,j}来表示方案数

fi,jf_{i,j}表示只考虑前i个物品时背包体积正好是j时的最大价值
gi,jg_{i,j}表示只考虑前i个物品时背包体积正好是j时的方案数

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
for (int i = 0; i < N; i++) {
  for (int j = V; j >= v[i]; j--) {
    int tmp = max(dp[j], dp[j - v[i]] + w[i]);
    int c = 0;
    if (tmp == dp[j]) c += cnt[j];                       // 如果从dp[j]转移
    if (tmp == dp[j - v[i]] + w[i]) c += cnt[j - v[i]];  // 如果从dp[j-v[i]]转移
    dp[j] = tmp;
    cnt[j] = c;
  }
}
int max = 0;  // 寻找最优解
for (int i = 0; i <= V; i++) {
  max = max(max, dp[i]);
}
int res = 0;
for (int i = 0; i <= V; i++) {
  if (dp[i] == max) {
    res += cnt[i];  // 求和最优解方案数
  }
}

求次优解&第k优解

第K优解比求最优解的复杂度上多一个系数K。其基本思想是，将每个状态都表示成有序队列，将状态转移方程中的max/min转化成有序队列的合并。

这里定义dp状态为fi,j,kf_{i,j,k}，表示前i个物品中，背包大小为v时，第k优解的值。所以fi,j,1...Kf_{i,j,1...K}就可以看成是fi−1,j,1...Kf_{i-1,j,1...K}和fi−1,j−vi,1...K+wif_{i-1,j-v_i,1...K}+w_i这两个序列合并后取前K项的结果

补充资料

背包问题九讲 - 崔添翼