Czj's Blog

第四讲-动态规划与背包思想

发表于 更新于 分类于 ，
本文字数： 7.5k 阅读时长 ≈ 7 分钟

作业链接

[蓝桥杯] 第四讲：动态规划与背包思想 - 题单 - 洛谷 | 计算机科学教育新生态

AC 代码

B3637 最长上升子序列 - 洛谷

问题类型：最长上升子序列（LIS）

解题思路：

  • 维护一个动态数组 ans，记录当前可能的递增序列。
  • 遍历每个数，若该数大于 ans 的末尾元素，直接加入；否则，用该数替换 ans 中第一个大于等于它的元素。
  • 最终 ans 的长度即为最长上升子序列的长度。

关键点：贪心策略结合二分查找优化时间复杂度到 O(n log n)。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
int n, x;
vector<int> ans;
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> x;
		if (ans.empty() || ans.back() < x) {
			ans.push_back(x);
		} else {
			int idx = lower_bound(ans.begin(), ans.end(), x) - ans.begin();
//			cout << idx << endl;
			ans[idx] = x;
		}
	}
	cout << ans.size();
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
import bisect

n = int(input())
m = list(map(int, input().split()))
a = []
for x in m:
    pos = bisect.bisect_left(a, x)
    if pos == len(a):
        a.append(x)
    elif a[pos] > x:
        a[pos] = x  # 仅当 a[pos] > x 时才替换（去重）

print(len(a))

P8707 [蓝桥杯 2020 省 AB1] 走方格 - 洛谷

问题类型：网格路径计数（动态规划）

解题思路：

  • 定义 dp[i][j] 为到达坐标 (i,j) 的路径数。
  • 初始化起点 dp[i][j] = 1。
  • 若当前格子行列均为偶数，则不可达（dp[i][j] = 0）；否则，路径数由上方和左方转移而来。
  • 最终输出 dp[n][m]。

关键点：处理禁止位置并累加有效路径。

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
#include<iostream>
using namespace std;
const int N = 35;
int n,m,dp[N][N];
int main()
{
    cin>>n>>m;
    for(int i = 1;i<=n;i++)
    {
        for(int j  = 1;j<=m;j++)
        {
            if(i==1&&j==1) dp[i][j] = 1;
            else if(i%2==0&&j%2==0)
            {
                dp[i][j] = 0;
            }
            else
            {
                dp[i][j] = dp[i-1][j]+dp[i][j-1];
            }
        }
    }
    cout<<dp[n][m]<<endl;
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
n, m = map(int, input().split())
dp = [[0]*(m+1) for _ in range(n+1)]
dp[1][1] = 1
for i in range(1, n+1):
    for j in range(1, m+1):
        if i == 1 and j == 1:
            continue
        if i % 2 == 0 and j % 2 == 0:
            dp[i][j] = 0
        else:
            dp[i][j] = dp[i-1][j] + dp[i][j-1]
print(dp[n][m])

P8786 [蓝桥杯 2022 省 B] 李白打酒加强版 - 洛谷

问题类型：三维动态规划（状态转移）

解题思路：

  • 状态 f[i][j][k] 表示遇到 i 次店、j 次花，剩余酒量为 k 的方案数。
  • 转移分两种情况：遇到店（酒量翻倍）或遇到花（酒量减 1）。
  • 最终结果为最后一次遇到花后的状态 f[n][m-1][1]（剩余 1 斗酒）。

关键点：合法状态转移及边界条件处理。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
#include<bits/stdc++.h>
using namespace std;
int n,m;
const int N = 1e2+9,M =  1000000007;
int f[N][N][N];
int main()
{
    cin>>n>>m;
    f[0][0][2] = 1;
    for(int i = 0;i<=n;i++)
    {
        for(int j = 0;j<=m;j++)
        {
            for(int k = 0;k<=m;k++)
            {
                int &val = f[i][j][k];
                if(i&&k%2==0) val = (val+f[i-1][j][k/2])%M;
                if(j) val = (val+f[i][j-1][k+1])%M;
            }
        }
    }
    cout<<f[n][m-1][1];
    return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
MOD = 10**9 + 7
n, m = map(int, input().split())
f = [[[0]*(m+2) for _ in range(m+1)] for __ in range(n+1)]
f[0][0][2] = 1

for i in range(n+1):
    for j in range(m+1):
        for k in range(m+1):
            if i > 0 and k % 2 == 0:
                f[i][j][k] = (f[i][j][k] + f[i-1][j][k//2]) % MOD
            if j > 0 and k + 1 <= m:
                f[i][j][k] = (f[i][j][k] + f[i][j-1][k+1]) % MOD

print(f[n][m-1][1] % MOD)

P1048 [NOIP 2005 普及组] 采药 - 洛谷

问题类型：01 背包问题

解题思路：

  • 将时间视为背包容量，每株草药的价值为收益。
  • 一维数组优化，逆序遍历时间避免重复选择。
  • 状态转移方程：dp[j] = max(dp[j], dp[j - time] + value)。
  • 输出 dp[t] 即最大总价值。

关键点：经典 01 背包实现，空间优化技巧。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
#include <bits/stdc++.h>
using namespace std;
int t, m;
const int N = 1e4 + 9;
int w[N], v[N], dp[N];
int main() {
	cin >> t >> m;

	for (int i = 0; i < m; i++) {
		cin >> w[i] >> v[i];
	}
	for (int i = 0; i < m; i++) {
		for (int j = t; j >= w[i]; j--) {
			dp[j] = max(dp[j], dp[j - w[i]] + v[i]);
		}
	}
	cout << dp[t];
	return 0;
}
1
2
3
4
5
6
7
t, m = map(int, input().split())
dp = [0]*(t+1)
for _ in range(m):
    cost, val = map(int, input().split())
    for j in range(t, cost-1, -1):
        dp[j] = max(dp[j], dp[j-cost] + val)
print(dp[t])

P8742 [蓝桥杯 2021 省 AB] 砝码称重 - 洛谷

问题类型：带权 01 背包（左右放置） 解题思路：

  • 每个砝码可放左、右或不用，状态转移需考虑加减当前重量。
  • 二维状态 dp[i][j] 表示前 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
#include<bits/stdc++.h>
using namespace std;
int n;
const int N = 1e2+9, M = 1e5+9;
int w[N], ans;
bool dp[N][M]; // dp[i][j] = 1 表示枚举到第 i 个砝码，质量 j 可以被表示
int main() {
	cin >> n;
	for (int i = 1; i <= n; i++) {
		cin >> w[i];
	}
	// 01 背包
	dp[0][0] = 1;
	// 可以称出的重量就是左侧砝码的总重量与右侧砝码的总重量之差的绝对值
	for (int i = 1; i <= n; i++) {
		for (int j = M; j >= 0; j--) {
			if (dp[i - 1][j])dp[i][j] = 1; // 不需要放
			if (j == w[i])dp[i][j] = 1; // 只放当前这一个砝码
			if (dp[i - 1][j + w[i]])dp[i][j] = 1; // 去掉 w[i]
			if (dp[i - 1][abs(j - w[i])])dp[i][j] = 1; // 加上 w[i]
		}
	}
	for (int i = 1; i < M; i++) {
		if (dp[n][i])ans++;
	}
	cout << ans;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
n = int(input())
w = list(map(int, input().split()))
M = 10**5 + 9
dp = [[False]*M for _ in range(n+1)]
dp[0][0] = True

for i in range(1, n+1):
    for j in range(M):
        if dp[i-1][j]:
            dp[i][j] = True
            if j + w[i-1] < M:
                dp[i][j + w[i-1]] = True
            dp[i][abs(j - w[i-1])] = True

print(sum(dp[n][1:]))

P2347 [NOIP 1996 提高组] 砝码称重 - 洛谷

问题类型：多重背包问题

解题思路：

  • 遍历每种砝码，枚举其数量，更新可能的质量组合。
  • 使用布尔数组 dp 记录可组成的质量。
  • 最终统计 dp 中为 true 的非零元素数量。

关键点：多重背包转化为 01 背包处理，注意组合方式。

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
#include<bits/stdc++.h>
using namespace std;
int w[] = {0, 1, 2, 3, 5, 10, 20}, a[10], ans;
const int N = 1e3+40;
bool dp[N]; // dp[i] = 1 表示质量 i 可以被组合出来
int main() {
	for (int i = 1; i <= 6; i++) { // 6 种砝码
		cin >> a[i]; // 第 i 种砝码有 a[i] 个
	}
	// 多重背包：枚举每个砝码，从大到小枚举可以组合出来的质量
	dp[0] = 1; // 初始化：一个都不选也是可以组合的
	for (int i = 1; i <= 6; i++) {
		for (int j = 1; j <= a[i]; j++) {
			for (int k = 1000; k >= 0; k--) {// 最大质量为 1e3
				if (dp[k]) {
//					cout << w[i] << " " << j << " " << k << endl;
					dp[k + w[i]] = 1;
				}
			}
		}
	}
	// 但在计算结果时不能考虑 dp[0] 因为题目强调不包括一个也不用的情况
	for (int i = 1; i < N; i++) {
		if (dp[i])ans++;
	}
	cout << "Total=" << ans << endl;
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
w = [0, 1, 2, 3, 5, 10, 20]
a = list(map(int, input().split()))
dp = [False]*(1001)
dp[0] = True

for i in range(1, 7):
    count = a[i-1]
    for _ in range(count):
        for j in range(1000, -1, -1):
            if dp[j] and j + w[i] <= 1000:
                dp[j + w[i]] = True

print(f"Total={sum(dp[1:])}")

P1616 疯狂的采药 - 洛谷

问题类型：完全背包问题

解题思路：

  • 允许无限地重复选择物品，正序遍历时间以支持多次选取。
  • 状态转移方程：dp[j] = max(dp[j], dp[j - time] + value)。
  • 输出最大价值 dp[t]。

关键点：完全背包的正序更新策略。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
#include <bits/stdc++.h>
using namespace std;
//完全背包问题
int t, m;
typedef long long ll;
const int N = 1e4 + 9, T = 1e7 + 9;
ll val[N], cost[N], f[T];
int main() {
	cin >> t >> m;
	for (int i = 1; i <= m; i++) {
		cin >> cost[i] >> val[i];
	}
	for (int i = 1; i <= m; i++) {
		for (int j = cost[i]; j <= t; j++) {
			//正序推，每个f[j]可以看作f[i-1][j]
			f[j] = max(f[j], f[j - cost[i]] + val[i]);//可以多选一个
		}
	}
	cout << f[t];
	return 0;
}
1
2
3
4
5
6
7
t, m = map(int, input().split())
dp = [0]*(t+1)
for _ in range(m):
    cost, val = map(int, input().split())
    for j in range(cost, t+1):
        dp[j] = max(dp[j], dp[j - cost] + val)
print(dp[t])

P8646 [蓝桥杯 2017 省 AB] 包子凑数 - 洛谷

问题类型：数论+完全背包

解题思路：

  • 若所有数互质（GCD 为 1），则存在最大不可组成的数，否则无限。
  • 完全背包标记可组成的数，统计未被标记的数量。
  • 使用布尔数组 dp 记录能组成的数。

关键点：裴蜀定理特判及完全背包求解。

关于第二重循环只需要枚举到 N∗N 的说明

由小凯的疑惑可知：两个互质的数字 p,q，不能表示的最大数是 p∗q−q−p，因此本题中：两个互质的数不能表示的最大数不会大于 N∗N−2×N，即不会大于 N∗N。同时我们发现，三个互质的数所不能表示的数，一定不会大于两个互质的数所不能表示的数。因为新增一个数字，能表示的数一定不会变少，即不会出现原来能表示的数变得不能表示了，也就是说，上界 p∗q−q−p 一定不会上移。

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
#include<bits/stdc++.h>
using namespace std;
/*
	数论 + 背包

	n 种蒸笼，每个可以放 ai 个包子，蒸笼的数量是无限的
	求有哪些 A 不能被 a1 * x1 + a2 * x2 + ai * xi + ... + an * xn 表示出来
	最简单的情况是两数之和为给定两个种蒸笼 a,b 其可以组合出：ax + by = m
	形式符合裴蜀定理，但要注意的是本题中 x,y 不能为负数，因此即使 gcd(ai) = 1 也不说明所有的整数都能被组合出来
*/
int n, ans, flg = 0; // 初始化为 0 避免对结果造成影响
const int N = 1e2+9, M = 1e5+9;

int a[N];
bool dp[M];
int gcd(int a, int b) {
	if (b == 0)return a;
	return gcd(b, a % b);
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++) {
		cin >> a[i];
//		flg = __gcd(flg,a[i]);
		flg = gcd(flg, a[i]);
	}
	if (flg != 1) {
		// 说明 ai 中的数字不是互质的，则必定有一些质数及它们的倍数无法被描述，因此无法被组合的数字个数为无限
		cout << "INF";
	} else {
		dp[0] = 1; // 初始化，默认 0 个包子是可以被组合出来的
		// 枚举所有的数字
		for (int i = 0; i < n; i++) {
			for (int j = a[i]; j < M; j++) {
				if (dp[j - a[i]])dp[j] = 1;
			}
		}
		for (int i = 0; i < M; i++) {
			if (!dp[i])ans++;
		}
		cout << ans;
	}
	return 0;
}
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
import math

n = int(input())
a = [int(input()) for _ in range(n)]
gcd_all = a[0]
for num in a[1:]:
    gcd_all = math.gcd(gcd_all, num)

if gcd_all != 1:
    print("INF")
else:
    max_val = 10**5
    dp = [False]*(max_val + 1)
    dp[0] = True
    for num in a:
        for j in range(num, max_val + 1):
            if dp[j - num]:
                dp[j] = True
    print(sum(not x for x in dp[1:max_val + 1]))