问题 A: 天使的爱情红箭
题目描述
为保证简单，本训练所有题面剧情均已做删减。
你相信天使吗？
Lonely 与他的女朋友分手后十分伤心，悲痛欲绝下来到天台。突然出现一只天使，她以为 Lonely 想要轻生，于是急忙制止，并说是来拯救 Lonely 的。天使自称是灵儿，Lonely 有着入骨的中二病，因此他对天使的出现表示非常惊喜。灵儿拿出一对翅膀，和一支射中别人便可以让TA爱上自己的红箭，问 Lonely 想要哪个。一个是能够自由地飞翔的翅膀，一个是能力非常强的红箭，权衡利弊之下，他选择了全都要。于是灵儿便把两者都给了 Lonely，表示自己是特级天使，可以让主人同时这拥有两种物品。
灵儿对 Lonely 说道：红箭拥有三级，等级越高消耗的身体能量越多，它们可以抽象为具体的数字，即分别为1,5,11点。天使可以看到人的身体承受上限，即最多可以承受多少点能量的红箭的攻击，只有红箭能量总和等于人的身体承受上限，才可以被控制。
Lonely 想要试试红箭的效果，于是他在路上随便找了一个小姐姐，灵儿告诉 Lonely 她的身体承受上限是 nnn点，Lonely 很快便知道他至少要使用多少红箭才可以控制小姐姐了。
输入
仅一行，一个正整数 nnn。
输出
仅一行，一个正整数，表示需要的红箭数。
输入输出样例
样例输入 #1
复制
15样例输出 #1
复制
3样例输入 #2
复制
12样例输出 #2
复制
2提示
对于样例数据 1，最佳方案是 15=5+5+515=5+5+515=5+5+5，使用到 3 个红箭。
对于样例数据 2，最佳方案是 12=11+112=11 + 112=11+1，使用到 2 个红箭。
对于 100%100\%100% 的数据，保证 n≤106n\leq 10^6n≤106。假设 Lonely 拥有无限的能量，即1,5,11的红箭无数个。
把递归顺序改成了
11 → 5 → 1，这样大的步长先走，能更快接近目标，减少递归深度。
#include<iostream> #include<vector> #define int long long using namespace std; int n; int ans = 0x3f3f3f3f; const int N = 1e6 + 10; vector<int>memo(N, 0x3f3f3f3f); void dfs(int i, int cnt) { if (i > n) return; if (cnt >= memo[i]) return; memo[i] = cnt; if (i == n) { ans = min(ans, cnt); return; } //把递归顺序改成了 11 → 5 → 1 //这样大的步长先走，能更快接近目标，减少递归深度。 dfs(i + 11, cnt + 1); dfs(i + 5, cnt + 1); dfs(i + 1, cnt + 1); } signed main() { cin >> n; dfs(0, 0); cout << ans; return 0; }问题 B: 巧合与陷阱
题目描述
WLY 提到，我们（1，1）到运动场（n，m）有些距离，应当规划一下如何飞。身为继承者的 WLY 也有翅膀，由于有翅膀，所以可以无视地面的障碍物，地图内所有的方格均可以进入。在两天使一人的注视下，聪明的 Lonely 看了一眼地图便说出了可能的走法有多少种。
输入
一行，两个正整数 nnn 和 mmm，代表身处 nnn 行 mmm 列的地图中。
输出
在保证 Lonely 和 WLY 小姐姐只能向下或者向右走的前提下，Lonely 走到运动场一共有多少种走法？
输入输出样例
样例输入 #1
复制
1 5样例输出 #1
复制
1样例输入 #2
复制
2 4样例输出 #2
复制
4样例输入 #3
复制
3 4样例输出 #3
复制
10提示
对于第一组样例，1×5 的地图大小，只有一条路可以走，即（1,1）-（1,5）
对于第二组样例，2×4 的地图大小，有四种走法：
（1,1）-（1,2）-（1,3）-（1,4）-（2,4）
（1,1）-（1,2）-（1,3）-（2,3）-（2,4）
（1,1）-（1,2）-（2,2）-（2,3）-（2,4）
（1,1）-（2,1）-（2,2）-（2,3）-（2,4）
对于 100%100\%100% 的数据，保证 n,m≤100n,m \leq 100n,m≤100。注意需要使用long long数据类型，题目保证答案的范围处于long long的范围内。
记得开long long。
#include<iostream> #include<vector> #define int long long using namespace std; signed main() { int n, m; cin >> n >> m; vector<vector<int>>dp(110, vector<int>(110)); for (int i = 0;i < 110;i++) { dp[i][1] = 1; dp[1][i] = 1; } for (int i = 2;i <= n;i++) { for (int j = 2;j <= m;j++) { dp[i][j] = dp[i - 1][j] + dp[i][j - 1]; //cout << dp[i][j] << " "; } //cout << "\n"; } cout << dp[n][m]; return 0; }问题 C: 隐匿深处的弱点
[提交] [视频] [状态]
题目描述
灵儿还是告诉了 Lonely 箭都存在的弱点：将白箭的上半部分抽象为金字塔形，共有 nnn 层，存在一些点，上面有脆弱度数字，从第一层开始，向下每层需要向左或者向右移动，并将路径上的数字累加，到达最底层（即白箭的过渡层）时，如果某点的路径中存在所有路径的最小的累加和，那么称这一点为这支箭的脆弱点。使用任意类型的箭攻击这一点即可摧毁该箭。
输入
第一行一个正整数 nnn，代表金字塔的层数。
下面 nnn 行，每行存在 iii 个正整数，iii 代表层数。
输出
输出从第一层到底层任意点的路径使得路径经过的数字之和最小的最小值。（每一步可以走到左下方的点也可以到达右下方的点）
输入输出样例
样例输入 #1
复制
5 13 11 8 12 7 26 6 14 15 8 12 7 13 24 11样例输出 #1
复制
49提示
13->8->7->14->7
对于 100%100\%100% 的数据，保证 1≤n≤1001 \leq n \leq 1001≤n≤100。金字塔中的数字不会超过 1000。
#include<iostream> #include<vector> #define int long long using namespace std; signed main() { int n; cin >> n; vector<vector<int>>tower(n, vector<int>(n)); for (int i = 0;i < n;i++) { for (int j = 0;j <= i;j++) cin >> tower[i][j]; } auto dp = tower; for (int i = n - 2;i >= 0;i--) { for (int j = 0;j <= i;j++) { dp[i][j] += min(dp[i + 1][j], dp[i + 1][j + 1]); } } cout << dp[0][0]; return 0; }问题 D: 就这？你也不想让我这么容易就进来吧？
题目描述
灵儿说，大叔是一级天使，拥有翅膀和红箭，但是没有白箭。而 WLY 是二级天使，只有翅膀。特级天使一共有三个。
大叔说他家中私藏了很多武器，可以提升他们的战斗力，弥补一下 WLY 和他没有白箭的短板。三人三天使讨论了一会，打算一同前往。
大叔家的底下仓库有个密码门，门上有一串数字，正好 nnn 个，大叔给出了两个提示，想看看 Lonely 能否猜出密码有几位：
1.密码是升序的
2.密码的位数要尽可能多
输入
第一行一个正整数 nnn，表示一共有 nnn 个数字。
第二行为 nnn 个正整数，a1 ,a2 ,a3 ,a4 ,a5 ,a6 ,a7 ....an
输出
求它的一个子序列（设为s1 ,s2 ,…sn），使得这个子序列满足这样的性质s1<s2<s3<...<sn，并且这个序列的长度最长。输出这个最长子序列的长度。
输入输出样例
样例输入 #1
复制
7 1 7 3 5 9 4 8样例输出 #1
复制
4提示
选择数字 1,3,4,8 或 1,3,5,8 均可以满足条件，故密码的位数为 4。
(1≤N≤1000)(1 \le N \le 1000)(1≤N≤1000)，数字的范围是 [0,10000][0, 10000][0,10000]。
最长上升子序列。
#include<iostream> #include<vector> #define int long long using namespace std; signed main() { int n; cin >> n; vector<int>a(n); for (int i = 0;i < n;i++) cin >> a[i]; vector<int>dp(n); //每个元素自身可以作为一个长度为 1 的上升子序列 for (int i = 0;i < n;i++) dp[i] = 1; for (int i = 0;i < n;i++) { for (int j = i;j < n;j++) { if (a[i] < a[j]) dp[j] = max(dp[i] + 1, dp[j]); } } //遍历整个 dp 数组，找出其中的最大值 //因为最长上升子序列不一定以最后一个元素结尾 int ans = 0; for (int i = 0;i < n;i++) ans = max(ans, dp[i]); cout << ans; return 0; }问题 E: 还没装够呢
题目描述
Lonely 一行人成功抵达大叔的地下密室，看到一堆武器装备，他们惊呆了。大叔分给 Lonely 一个容积为 MMM 大背包，让他们挑选自己觉得用得上的带走就行。他们一时竟然不知道选什么好。灵儿帮助他们数出一共有 NNN 种物品（每种物品只有一件），并分析出了物品的重量 wiw_iwi 和她认为的价值 did_idi (wi,di<=231−1)(w_i,d_i<=2^{31}-1)(wi,di<=231−1)。想要让背包尽可能装满的同时要让价值最大化，这下轮到 Lonely 头痛了，不过有贴心的 WLY 在旁，“我来帮你吧~收拾东西什么的我可擅长了”。(N≤3500,M≤13000)(N \le 3500, M \le 13000)(N≤3500,M≤13000)
输入
第一行是整数 NNN 和 MMM。
第二行到第 N+1N+1N+1 行：每行两个整数 WWW 和 DDD ，描述一个物品的体积和价值。
输出
输出一个整数，表示能放入背包的物品的最大价值总和。
输入输出样例
样例输入 #1
复制
4 6 1 4 2 6 3 12 2 7样例输出 #1
复制
2301背包。
#include<iostream> #include<vector> #define int long long using namespace std; signed main() { int n, V; cin >> n >> V; vector<int>v(n+1); vector<int>w(n+1); for (int i = 1;i <= n;i++) { cin >> v[i] >> w[i]; } vector<vector<int>>dp(n + 1, vector<int>(V + 1)); for (int i = 1;i <= n;i++) { for (int j = 0;j <= V;j++) { dp[i][j] = dp[i - 1][j]; if (j >= v[i]) dp[i][j] = max(dp[i][j], dp[i - 1][j - v[i]] + w[i]); } } cout << dp[n][V]; return 0; }问题 F: 学会正确使用翅膀很关键！
题目描述
打包完毕！
他们现在要赶往大叔被困地，距离为 nnn ，利用翅膀的迭进能力，可以更迅速的到达，但是要注意不要超过距离 nnn。
如果使用迭进能力，则可以双倍已经行驶过的路程，否则路程+1。
换句话说，假设现在已经前进了 xxx 距离，可以选择将距离变为 2x2x2x，或者 x+1x+1x+1，无论选择哪一项，都视为飞行次数+1。
初始时路程为 1。
输入
仅一行，一个正整数 nnn。
输出
仅一行，一个正整数，表示最少飞行次数。
输入输出样例
样例输入 #1
复制
16样例输出 #1
复制
4样例输入 #2
复制
5样例输出 #2
复制
3提示
样例数据1，1→2→4→8→161\to 2\to 4\to8\to 161→2→4→8→16，共 4 次。
样例数据2，1→2→4→51\to 2\to 4\to 51→2→4→5，共 3 次。
对于 100%100\%100% 的数据，n≤106n\leq 10^6n≤106。
这题说实话我没有dp的思路，第一想法是dfs。然后第一次dfs还超时了，因为没有开记忆数组。
#include<iostream> #include<vector> #define int long long using namespace std; int n; int ans = 0x3f3f3f3f; const int N = 1e7 + 10; //记得开记忆数组，不然会超时。 vector<int>memo(N, 0x3f3f3f3f); void dfs(int i, int cnt) { if (i > n) return; if (cnt >= memo[i]) return; memo[i] = cnt; if (i == n) { ans = min(ans, cnt); return; } dfs(i + 1, cnt + 1); dfs(i * 2, cnt + 1); } signed main() { cin >> n; dfs(1, 0); cout << ans; return 0; }问题 G: 放置自动弩
题目描述
无论是灵儿说出的话，还是她所拥有的【红箭】和【白箭】，都使 Lonely 不得不吐槽她到底是天使还是魔鬼。灵儿却对此不以为然，她认为并无恶魔这种东西，要真说，恶魔也只存在于人心中。Lonely 询问灵儿能否帮忙计算一下自动弩放在哪里比较好，灵儿想了想，给他推荐出了 nnn 个放置自动弩的地点，用m1,m2,…,mnm_1, m_2, \dots , m_nm1,m2,…,mn 来表示他们的相对位置。
由于地段关系，每个地点会产生的影响不同，灵儿给出了她预估的每处可能产生的影响力，用 pip_ipi 表示在 mim_imi 处放置自动弩的影响力。为了避免自动弩被快速破坏，弩之间的距离必须大于 kkk。在二人二天使的商讨下，他们很快就找到了最合适放置自动弩的几个地点。
输入
输入包含若干组测试数据。
第一行是整数 TTT (1≤T≤1000)(1 \le T \le 1000)(1≤T≤1000)，表明有 TTT 组测试数据。
紧接着有 TTT 组连续的测试。每组测试数据有 333 行。
第 111 行: 地点总数 nnn (n<100)(n \lt 100)(n<100)，距离限制 kkk (0<k<1000)(0 \lt k \lt 1000)(0<k<1000)。
第 222 行: nnn 个地点的位置 m1,m2,…,mnm_1, m_2, \dots, m_nm1,m2,…,mn (0<mi<1000000(0 \lt m_i \lt 1000000(0<mi<1000000 且为整数，升序排列)))。
第 333 行: nnn 个地点的影响力 p1,p2,…,pnp_1, p_2, \dots, p_np1,p2,…,pn (0<pi<1000(0 \lt p_i \lt 1000(0<pi<1000 且为整数)))。
输出
对于每组测试数据可能的最大影响力。
输入输出样例
样例输入 #1
复制
2 3 11 1 2 15 10 2 30 3 16 1 2 15 10 2 30样例输出 #1
复制
40 30提示
在第一组数据中，选择在位置 1 和位置 15 的地点，总影响力为40。由于距离之间必须大于11，所以 2 位置无法放置弩。
假设弩是无限的，你只需要选择地点并计算最大影响力即可。
#include<iostream> #include<algorithm> #include<vector> #define int long long using namespace std; struct node { int val;//影响力 int pos;//位置 }; bool cmp(struct node a, struct node b) { return a.pos < b.pos; } signed main() { int t; cin >> t; while (t--) { // n:地点数量，k:最小距离限制 int n, k; cin >> n >> k; vector<struct node>place(n); for (int i = 0;i < n;i++) cin >> place[i].pos; for (int i = 0;i < n;i++) cin >> place[i].val; //将所有地点按位置从小到大排序 sort(place.begin(), place.end(), cmp); //dp[i]表示考虑前i+1个地点时的最大总影响力 vector<int>dp(n); int maxn = 0; for (int i = 0;i < n;i++) { //每个地点至少可以只选自己 //所以初始值设为自己的影响力 dp[i] = place[i].val; } for (int i = 0;i < n;i++) { //看前面哪些位置可以搭配 for (int j = 0;j < i;j++) { //地点i和地点j的距离是否大于k if (place[i].pos > place[j].pos + k) { //dp[i] = max(原来的值, 选j的最优解 + 选i的价值) dp[i] = max(dp[i], dp[j] + place[i].val); } } //也可以不选当前位置，继承前面的最优解 if (i > 0) dp[i] = max(dp[i], dp[i - 1]); } //考虑所有n个地点时的最大总影响力 cout << dp[n - 1] << "\n"; } return 0; }问题 H: 仅剩的可能性
题目描述
准备完毕，排列分散的自动弩接连射出，看守者们一个个被击中，依次倒下......射出的那是...白箭！Lonely 不可置信地看向灵儿，虽然她没有办法影响到世界，但是可以改变她的箭。“目的达到了就好啦~”天使灵儿在旁边莞尔一笑，不禁让 Lonely 毛骨悚然。在那一刻，Lonely 甚至分不清灵儿到底是想要救人还是杀人，或许继承者对她来说更为重要吧。
门开了，大叔出来了，表现的很虚弱。他仿佛已经支撑不住，拼命想说什么，不知为何却说不出口。大叔用手在地上写下了一些数字，便永远的倒了下去。
Lonely 知道，这是他们之间约定的密码，包含字母 A-Z 的消息会通过以下映射进行编码 ：
‘A’ -> “1”
‘B’ -> “2”
…
‘Z’ -> “26”
要 解码 已编码的消息，所有数字必须基于上述映射的方法，反向映射回字母（可能有多种方法）。例如，“11106” 可以映射为：
“AAJF” ，将消息分组为 (1 1 10 6) “KJF” ，将消息分组为 (11 10 6) 注意，消息不能分组为 (1 11 06) ，因为 “06” 不能映射为 “F” ，这是由于 “6” 和 “06” 在映射中并不等价。
Lonely 很快算出了一共有多少种解码方法，但是大叔好像并没有告诉怎么分割啊！灵儿在旁边看着这一切，突然像是想到了什么，“不好，快走！”。
输入
输入一行，只包含一个只含数字的非空字符串 s。
输出
返回解码方法的总数 。
题目数据保证答案肯定是一个 32 位 的整数。
输入输出样例
样例输入 #1
226样例输出 #1
3样例输入 #2
06样例输出 #2
0
