这是一个典型的动态规划问题。

由于每一天的寒潮判定只依赖于当天的气温和前一天的气温，且我们需要求解的是全局的最值（最大次数和最小次数），同时数据规模较小（，气温范围仅101个整数），这非常适合使用DP来解决。

算法思路

我们需要维护到第 天为止，且第 天气温为 时，所能产生的最大和最小寒潮次数。

状态定义： 我们需要两个二维数组（DP表）：

  • ：表示第 天的气温为 时，前 天里发生的寒潮次数的最大值。
  • ：表示第 天的气温为 时，前 天里发生的寒潮次数的最小值。

注意： 气温 的取值范围是 。在实际代码实现中，由于数组下标不能为负数，通常会将气温加上一个偏移量（例如 +50），将其映射到 的区间。

状态转移方程

对于第 天（ 从 2 到 ），我们需要枚举第 天所有可能的气温 ，以及第 天所有可能的气温 。

判定条件： 如果 （即前一天气温 减去当天气温 大于等于阈值 ），则说明发生了一次寒潮，记增量 ；否则 。

转移逻辑：

  • 最大值更新：
  • 最小值更新：

约束处理：

  • 如果输入数据中第 天的气温是已知的（即 ），那么 只能取 这个特定值。
  • 如果第 天气温未知，则 可以遍历 所有的值。
  • 同理，对于前一天 的气温 也要遵循输入数据的约束。

复杂度分析

时间复杂度：

  • 我们需要遍历 天。
  • 每一天我们需要枚举当天的气温（约100种可能）和前一天的气温（约100种可能）。
  • 设 为气温的值域大小（这里 ）。
  • 总时间复杂度为 。
  • 代入数据： 次运算。这在常规的时间限制（通常是 1秒 / 次运算）内是非常安全的，可以轻松通过。

空间复杂度：

  • 我们需要两个 的二维数组。
  • 总空间复杂度为 。
  • 代入数据： 的整型数组非常小，内存占用完全不是问题。
  • 优化空间： 由于第 天的状态只依赖于第 天，可以使用滚动数组将空间优化到 ，但在本题的数据规模下没有必要。

代码实现

#include <bits/stdc++.h>
using namespace std;
using ll = long long;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n, x;
    cin >> n >> x;

    const int Unknown = -999;
    vector<int> a(n);

    for (int i = 0; i < n; i++) {
        cin >> a[i];
    }

    vector<vector<int>> dp1(n, vector<int>(101, -1)); // 寒潮次数的最大值
    vector<vector<int>> dp2(n, vector<int>(101, 10001)); // 寒潮次数的最小值
    if (a[0] != Unknown) {
        int idx = a[0] + 50;
        dp1[0][idx] = 0;
        dp2[0][idx] = 0;
    } else {
        for (int i = 0; i <= 100; i++) {
            dp1[0][i] = 0;
            dp2[0][i] = 0;
        }
    }

    for (int i = 1; i < n; i++) {
        for (int j = 0; j <= 100; j++) {
            if (a[i] != Unknown && j != a[i] + 50)
                continue;
            for (int k = 0; k <= 100; k++) {
                if (a[i - 1] != Unknown && k != a[i - 1] + 50)
                    continue;
                int inc;
                if (k - j >= x)
                    inc = 1;
                else
                    inc = 0;
                dp1[i][j] = max(dp1[i][j], dp1[i - 1][k] + inc);
                dp2[i][j] = min(dp2[i][j], dp2[i - 1][k] + inc);
            }
        }
    }

    int ans_max = *max_element(dp1[n - 1].begin(), dp1[n - 1].end());
    int ans_min = *min_element(dp2[n - 1].begin(), dp2[n - 1].end());
    cout << ans_max << " " << ans_min << endl;

}