C++ 笔试刷题：模拟、动态规划与回文判断

一、小易的升级之路

题目描述

游戏角色初始能力值为 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]。

代码实现

注意数组下标对应关系。