前言
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第十五讲：复杂dp【习题】
本篇博客所包含习题有：
👊包子凑数
👊括号配对
👊旅游规划
复杂dp【例题】见博客：蓝桥杯第十五讲–复杂dp【例题】
如果你觉得本章节有些难度，建议先修如下两篇博客：
蓝桥杯第六讲–简单dp【例题】
蓝桥杯第六讲–简单dp【习题】
博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！
包子凑数
来源： 第八届蓝桥杯省赛C++A/B组,第八届蓝桥杯省赛JAVAA/B组
题目要求
题目描述：
输入格式：
输出格式：
输出一个整数代表答案。
如果凑不出的数目有无限多个，输出INF。
数据范围：
输入样例1：
2 4 5
输出样例1：
6
输入样例2：
2 4 6
输出样例2：
INF
样例解释：
对于样例 1，凑不出的数目包括：1 , 2 , 3 , 6 , 7 , 11 。
对于样例 2 ，所有奇数都凑不出来，所以有无限多个。
思路分析
二维空间的写法（朴素写法）
#include <cstdio> #include <algorithm> using namespace std; const int N = 10010; int a[110]; bool f[110][N]; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int main() { int n; scanf("%d", &n); int d = 0; for (int i = 1; i <= n; i ++ ) { scanf("%d", &a[i]); d = gcd(d, a[i]); } if (d != 1) puts("INF"); else { f[0][0] = true; for (int i = 1; i <= n; i ++ ) for (int j = 0; j < N; j ++ ) { f[i][j] = f[i - 1][j]; if (j >= a[i]) f[i][j] |= f[i][j - a[i]]; } int res = 0; for (int i = 0; i < N; i ++ ) if (!f[n][i]) res ++ ; printf("%d\n", res); } return 0; }
优化完空间后的写法
#include <cstdio> #include <algorithm> using namespace std; const int N = 10010; int a[110]; bool f[N]; int gcd(int a, int b) { return b ? gcd(b, a % b) : a; } int main() { int n; scanf("%d", &n); int d = 0; for (int i = 1; i <= n; i ++ ) { scanf("%d", &a[i]); d = gcd(d, a[i]); } if (d != 1) puts("INF"); else { f[0] = true; for (int i = 1; i <= n; i ++ ) for (int j = a[i]; j < N; j ++ ) f[j] |= f[j - a[i]]; int res = 0; for (int i = 0; i < N; i ++ ) if (!f[i]) res ++ ; printf("%d\n", res); } return 0; }
括号配对
题目要求
题目描述：
输入格式：
输入仅一行，为字符串BE。
输出格式：
输出仅一个整数，表示增加的最少字符数。
数据范围：
对于所有输入字符串，其长度小于100。
输入样例：
[])
输出样例：
1
思路分析
代码
#include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 110, INF = 100000000; int n; int f[N][N]; bool is_match(char l, char r) { if (l == '(' && r == ')') return true; if (l == '[' && r == ']') return true; return false; } int main() { string s; cin >> s; n = s.size(); for (int len = 1; len <= n; len ++ ) for (int i = 0; i + len - 1 < n; i ++ ) { int j = i + len - 1; f[i][j] = INF; if (is_match(s[i], s[j])) f[i][j] = f[i + 1][j - 1]; if (j >= 1) f[i][j] = min(f[i][j], min(f[i][j - 1], f[i + 1][j]) + 1); for (int k = i; k < j; k ++ ) f[i][j] = min(f[i][j], f[i][k] + f[k + 1][j]); } cout << f[0][n - 1] << endl; return 0; }
旅游规划
题目要求
题目描述：
输入格式：
输出格式：
输出包括若干行，每行包括一个整数——某个位于最长路径上的路口编号。
为了确保解唯一，请将所有最长路径上的路口编号按编号顺序由小到大依次输出。
数据范围：
输入样例：
10 0 1 0 2 0 4 0 6 0 7 1 3 2 5 4 8 6 9
输出样例：
0 1 2 3 4 5 6 8 9
思路分析
代码
#include <cstdio> #include <cstring> #include <iostream> #include <algorithm> using namespace std; const int N = 200010, M = N * 2; int n; int h[N], e[M], ne[M], idx; int d1[N], d2[N], p1[N], up[N]; int maxd; void add(int a, int b) { e[idx] = b, ne[idx] = h[a], h[a] = idx ++ ; } void dfs_d(int u, int father) { for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (j != father) { dfs_d(j, u); int distance = d1[j] + 1; if (distance > d1[u]) { d2[u] = d1[u], d1[u] = distance; p1[u] = j; } else if (distance > d2[u]) d2[u] = distance; } } maxd = max(maxd, d1[u] + d2[u]); } void dfs_u(int u, int father) { for (int i = h[u]; ~i; i = ne[i]) { int j = e[i]; if (j != father) { up[j] = up[u] + 1; if (p1[u] == j) up[j] = max(up[j], d2[u] + 1); else up[j] = max(up[j], d1[u] + 1); dfs_u(j, u); } } } int main() { scanf("%d", &n); memset(h, -1, sizeof h); for (int i = 0; i < n - 1; i ++ ) { int a, b; scanf("%d%d", &a, &b); add(a, b), add(b, a); } dfs_d(0, -1); dfs_u(0, -1); for (int i = 0; i < n; i ++ ) { int d[3] = {d1[i], d2[i], up[i]}; sort(d, d + 3); if (d[1] + d[2] == maxd) printf("%d\n", i); } return 0; }
