C/C++每日一练19

第一题：小易的升级之路

题目描述：小易初始攻击力为 a，有 n 个怪兽，每个怪兽有防御力 x [i] 和攻击力 y [i]。若小易当前攻击力 > x [i]，则击败怪兽后攻击力增加 y [i]，否则无法击败。求小易最终的攻击力。算法原理：每次选择防御力最低的怪兽击败，才能最大化攻击力提升。所以先将怪兽按防御力升序排序，然后依次判断能否击败，能击败则累加攻击力，直到无法击败或击败所有怪兽。代码：

cpp

运行

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int n, a; cin >> n >> a; vector<pair<int, int>> monsters(n); for (int i = 0; i < n; ++i) { cin >> monsters[i].first >> monsters[i].second; } sort(monsters.begin(), monsters.end()); for (auto& m : monsters) { if (a > m.first) { a += m.second; } else { break; } } cout << a << endl; return 0; }

第二题：礼物的最大价值

题目描述：m×n 的网格中，每个格子有礼物价值，从左上角出发，每次只能向右或向下移动，求到达右下角的最大礼物价值。算法原理：动态规划。设 dp [i][j] 为到达 (i,j) 的最大价值，转移方程 dp [i][j] = max (dp [i-1][j], dp [i][j-1]) + grid [i][j]。边界：第一行只能从左向右，dp [0][j] = dp [0][j-1] + grid [0][j]；第一列只能从上到下，dp [i][0] = dp [i-1][0] + grid [i][0]。可优化为一维数组 dp [j]，每次更新时 dp [j] = max (dp [j], dp [j-1]) + grid [i][j]。代码：

cpp

运行

#include <iostream> #include <vector> #include <algorithm> using namespace std; int main() { int m, n; cin >> m >> n; vector<vector<int>> grid(m, vector<int>(n)); for (int i = 0; i < m; ++i) { for (int j = 0; j < n; ++j) { cin >> grid[i][j]; } } vector<int> dp(n, 0); dp[0] = grid[0][0]; for (int j = 1; j < n; ++j) { dp[j] = dp[j-1] + grid[0][j]; } for (int i = 1; i < m; ++i) { dp[0] += grid[i][0]; for (int j = 1; j < n; ++j) { dp[j] = max(dp[j], dp[j-1]) + grid[i][j]; } } cout << dp[n-1] << endl; return 0; }

第三题：对称之美

题目描述：判断一个字符串是否是回文串，即正读和反读都一样，例如 “abcba” 是回文串，“abca” 不是。算法原理：双指针法。左指针从字符串开头，右指针从结尾，依次比较两个指针指向的字符是否相等。若所有对应字符都相等则是回文串，否则不是。代码：

cpp

运行

#include <iostream> #include <string> using namespace std; int main() { string s; cin >> s; int left = 0, right = s.size() - 1; bool is_palindrome = true; while (left < right) { if (s[left] != s[right]) { is_palindrome = false; break; } left++; right--; } cout << << endl; return 0; }