360笔试 - 0914

第一题

题面

某个公司的共享单车单次骑行 $1$ 元，但可购买VIP卡免去骑行费用，有以下几种VIP卡：

• 日卡 $a$ 元，$1$ 天不收费；
• 月卡 $b$ 元，$30$ 天不收费；
• 年卡 $c$ 元，$365$ 天不收费；
• 十年卡 $d$ 元，$3650$ 天不收费。

每天都允许购入任意张VIP卡，生效时间可累加。

小A在未来 $n$ 天都需要骑共享单车，第 $i$ 天需要骑行 r[i] 次，现在小A想知道，他最少以要花多少钱。

输入描述：
第一行一正整数 $n(1≤n≤10^5)$。
第二行四个正整数 $a,b,c,d(1≤a,b,c,d≤10^7)$，表示四种卡的价格。
第三行 $n$ 个正整数 $r_i$，表示每天骑行次数。

输出描述:
输出一个整数 x，表示最小花费。

思路与代码

动态规划。

定义一个长度为 $n$ 的 DP数组，dp[i] 表示第 $i$ 天的最小花费。

遍历每一天，维护办卡和不办卡的情况下每天的最小花费。

$$dp[i] = min(dp[i] + dp[i - 1] + r[i])$$

#include <iostream>
#include <vector>
#include <algorithm>
#define ll long long
using namespace std;

int main() {
    int n;
    cin >> n;
    vector<int> prices(4);
    for (int i = 0; i < 4; ++i) cin >> prices[i];
    vector<int> rides(n);
    for (int i = 0; i < n; ++i) cin >> rides[i];

    vector<ll> dp(n + 1, 1e18);
    dp[0] = 0;
    for (int i = 0; i < n; ++i) {
        dp[i + 1] = min(dp[i + 1], dp[i] + rides[i]);
        for (int j = 0; j < 4; ++j) {
            // 考虑每种情况
            int days = (j == 0 ? 1 : (j == 1 ? 30 : (j == 2 ? 365 : 3650)));
            if (i + days <= n) {
                dp[i + days] = min(dp[i + days], dp[i] + prices[j]);
            }
        }
    }

    cout << dp[n] << endl;

    return 0;
}

第二题

题面

在盘古开天辟地之前，他需要对当前所处的地形进行调查。

盘古的面前一共有 $n$ 座山，从左往右第 $i$ 座山的高度为 $h_i$。盘古会选择一段连续的山进行开辟，记他选择的区间为 [l,r]，盘古选择的山必须满足 $h_l<h_{l+1}<...<h_r$，也就是从左往右对应山的高度严格单调递增。

盘古在开山之前，可以选择任意一座山，将其高度修改为任意非负整数值。由于种种限制，该操作最多进行一次。盘古想知道：他能够选择的区间最长是多少？

输入描述：
第一行一个正整数 $T$，表示数据组数。
对于每一组数据，第一行一个正整数 $n$，表示一共有 $n$ 座山，第二行输入 $n$ 个正整数 $h_1,h_2,...,h_n$。$(1≤n≤10^5,1≤T≤5,1≤h_i≤10^5)$

输出描述：
对于每一组数据，输出一行一个正整数，表示盘古能够选择的最长的区间对应的长度。

思路与代码

首先，需要找到不在进行任何修改的情况下，最长的严格单调递增子序列的长度。

然后，尝试通过修改一次任意一座山的高度，来最大化这个子序列的长度。

1. 预处理最长递增子序列：

   • 计算从左到右和从右到左的最长递增子序列的长度。
   • 具体来说，维护两个数组 l 和 r，其中 l[i] 表示从左到右以第 $i$ 座山结尾的最长递增子序列的长度，r[i] 表示从右到左以第 $i$ 座山结尾的最长递增子序列的长度。

2. 计算修改一次后的最长递增子序列：

   • 遍历每一座山 $i$，假设我们修改第 $i$ 座山的高度，使得它能够连接 l[i - 1] 和 r[i + 1] 的子序列。
   • 具体来说，我们需要检查 h[i - 1] < (h[i + 1] - 1) 是否成立（因为是严格递增，所以还需要 $-1$），如果成立，则可以通过修改 h[i] 使得 l[i - 1] 和 r[i + 1] 的子序列连接起来。

3. 计算通过修改第 $i$ 座山高度所能得到的最长递增子序列的长度，并更新全局最大值。

#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;

int main() {
    int T;
    cin >> T;
    while (T--) {
        int n;
        cin >> n;
        vector<int> h(n);
        for (int i = 0; i < n; ++i) cin >> h[i];

        vector<int> l(n, 1), r(n, 1);
        for (int i = 1; i < n; ++i) {
            if (h[i] > h[i - 1]) l[i] = l[i - 1] + 1;
        }
        for (int i = n - 2; i >= 0; --i) {
            if (h[i] < h[i + 1]) r[i] = r[i + 1] + 1;
        }

        int mx = 1;
        for (int i = 0; i < n; ++i) {
            mx = max(mx, l[i]);
        }

        for (int i = 1; i < n - 1; ++i) {
            if (h[i - 1] < (h[i + 1] + 1)) {
                mx = max(mx, l[i - 1] + r[i + 1]);
            }
        }

        // 最后要加上中间修改的山
        cout << mx + 1 << endl;
    }

    return 0;
}