牛客春招刷题训练营-2025.4.29题解

活动地址： 牛客春招刷题训练营 - 编程打卡活动

简单题 游游的数字圈

将输入的数字当做字符串，遍历字符串内字符统计答案。

#include <bits/stdc++.h>
using namespace std;
int main() {
    string s;
    cin >> s;
    int ans = 0;
    for (auto it : s) {
        if (it == '0' || it == '6' || it == '9')ans++;
        if (it == '8')ans += 2;
    }
    cout << ans;
    return 0;
}

中等题 最小花费爬楼梯

dp。
状态设计： 为爬到下标为 的台阶所需费用。
转移方程：

1. 如果 或 ，则 。
2. 否则 。

输出 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n), dp(n + 1, 1e9);
    for (int i = 0; i < n; i++)
        cin >> a[i];
    dp[0] = 0;
    dp[1] = 0;
    for (int i = 0; i < n; i++) {
        if (i + 1 <= n)
            dp[i + 1] = min(dp[i + 1], dp[i] + a[i]);
        if (i + 2 <= n)
            dp[i + 2] = min(dp[i + 2], dp[i] + a[i]);
    }
    cout << dp[n] << '\n';
    return 0;
}

困难题 取数游戏

区间dp。
状态设计： 是取数取到只剩区间 时可获得的最大价值。
首先得到 。
之后的思想是从短区间逐步逆推到区间 ，先枚举 从 到 ，对一段长度为 的区间 ，因为取数只能从区间左端点或者右端点取，也就是只能从 和 转移而来，这一步是第 次取数，所以 的下标为 ，转移方程为：
。
答案即为 。

#include <bits/stdc++.h>
using namespace std;
int main() {
    int n;
    cin >> n;
    vector<int> a(n + 1), b(n + 1);
    for (int i = 1; i <= n; i++)
        cin >> a[i];
    for (int i = 1; i <= n; i++)
        cin >> b[i];
    vector<vector<long long>> dp(n + 1, vector<long long>(n + 1));
    for (int i = 1; i <= n; i++)
        dp[i][i] = a[i] * b[n];
    for (int len = 2; len <= n; len++) {
        for (int i = 1; i + len - 1 <= n; i++) {
            int l = i, r = i + len - 1;
            dp[l][r] = max(dp[l + 1][r] + 1ll * a[l] * b[n - len + 1],
                           dp[l][r - 1] + 1ll * a[r] * b[n - len + 1]);
        }
    }
    cout << dp[1][n] << '\n';
    return 0;
}