一、小易的升级之路
题目描述
游戏角色初始能力值为 a,遇到 n 个怪物,防御值为 b1, b2...。若能力值 >= 怪物防御值,能力值加 bi;否则能力值加当前能力值和 bi 的最大公约数。求最终能力值。
算法思路
直接模拟整个过程。遍历每个怪物,根据条件更新能力值。
代码实现
注意多组输入。
#include <iostream>
#include <algorithm>
using namespace std;
int gcd(int x, int y) {
int tmp = x % y;
while (tmp) {
x = y;
y = tmp;
tmp = x % y;
}
return y;
}
int main() {
int c, n;
while (cin >> n >> c) {
for (int i = 0; i < n; i++) {
int x;
cin >> x;
if (c >= x) c += x;
else c += gcd(x, c);
}
cout << c << endl;
}
return 0;
}
二、礼物的最大价值
题目描述
m*n 棋盘,格子有礼物价值。从左上角 (0,0) 出发,只能向右或向下移动至右下角 (m-1,n-1),求最大礼物价值。
算法思路
动态规划。dp[i][j] 表示走到 [i,j] 位置能拿到礼物的最大价值。状态转移方程:dp[i][j] = max(dp[i][j-1], dp[i-1][j]) + arr[i][j]。
代码实现
注意数组下标对应关系。


