前言
蓝桥杯官网：蓝桥杯大赛——全国大学生TMT行业赛事
✨本博客讲解 蓝桥杯C/C++ 备赛所涉及算法知识，此博客为第十五讲：复杂dp【例题】
本篇博客所包含习题有：
👊鸣人的影分身
👊糖果
👊密码脱落
👊生命之树
复杂dp【习题】见博客：蓝桥杯第十五讲–复杂dp【习题】
如果你觉得本章节有些难度，建议先修如下两篇博客：
蓝桥杯第六讲–简单dp【例题】
蓝桥杯第六讲–简单dp【习题】
博客内容以题代讲，通过讲解题目的做法来帮助读者快速理解算法内容，需要注意：学习算法不能光过脑，更要实践，请读者务必自己敲写一遍本博客相关代码！！！
鸣人的影分身
题目要求
题目描述：
在火影忍者的世界里，令敌人捉摸不透是非常关键的。
我们的主角漩涡鸣人所拥有的一个招数——多重影分身之术——就是一个很好的例子。
影分身是由鸣人身体的查克拉能量制造的，使用的查克拉越多，制造出的影分身越强。
针对不同的作战情况，鸣人可以选择制造出各种强度的影分身，有的用来佯攻，有的用来发起致命一击。
那么问题来了，假设鸣人的查克拉能量为 M ，他影分身的个数最多为 N ，那么制造影分身时有多少种不同的分配方法？
注意：
- 影分身可以分配0点能量。
- 分配方案不考虑顺序，例如：M=7,N=3，那么 (2,2,3) 和(2,3,2) 被视为同一种方案。
输入格式：
第一行是测试数据的数目 t 。
以下每行均包含二个整数 M 和 N ，以空格分开。
输出格式：
对输入的每组数据 M 和 N ，用一行输出分配的方法数。
数据范围：
0≤t≤20,
1≤M,N≤10
输入样例：
1 7 3
输出样例：
8
思路分析
代码
#include <cstdio> #include <algorithm> using namespace std; const int N = 11; int main() { int T; scanf("%d", &T); while (T -- ) { int n, m; scanf("%d%d", &m, &n); int f[N][N] = {0}; f[0][0] = 1; for (int i = 0; i <= m; i ++ ) for (int j = 1; j <= n; j ++ ) { f[i][j] = f[i][j - 1]; if (i >= j) f[i][j] += f[i - j][j]; } printf("%d\n", f[m][n]); } return 0; }
糖果
题目要求
题目描述：
输入格式：
输出格式：
符合要求的最多能达到的糖果总数，如果不能达到 K 的倍数这一要求，输出 0 。
数据范围：
输入样例：
5 7 1 2 3 4 5
输出样例：
14
样例解释：
Dzx 的选择是 2 + 3 + 4 + 5 = 14，这样糖果总数是 7的倍数，并且是总数最多的选择。
思路分析
代码
#include <cstdio> #include <cstring> using namespace std; const int N = 110; int n, k; int f[N][N]; int max(int x, int y) { return x > y ? x : y; } int main() { scanf("%d%d", &n, &k); memset(f, -0x3f, sizeof f); f[0][0] = 0; for (int i = 1; i <= n; i ++ ) { int w; scanf("%d", &w); for (int j = 0; j < k; j ++ ) f[i][j] = max(f[i - 1][j], f[i - 1][(j + k - w % k) % k] + w); } printf("%d\n", f[n][0]); return 0; }
