题解 | 降温（easy）

发现状态只和前一天的温度有关；因此考虑当前天数与这天的温度作为状态，直接dp求解即可

#include <iostream>
#include <vector>
#define rep(i,x,y) for(int i=x;i<=y;i++)
using namespace std;

int main() {
    int n,x; cin >> n >> x;
    vector<int> a(n+5);
    rep(i,1,n) {
        cin >> a[i];
        a[i] += 50;
    }
    auto f = vector(n + 5, vector(107, -114514));
    auto g = vector(n + 5, vector(107, 114514));
    if(a[1] >= 0) f[1][a[1]] = g[1][a[1]] = 0;
    else {
        rep(j,0,100)
            f[1][j] = g[1][j] = 0;
    }
    rep(i,2,n) {
        if(a[i] >= 0) {
            rep(j,0,100) {
                f[i][a[i]] = max(f[i][a[i]], f[i-1][j] + (j - a[i] >= x));
                g[i][a[i]] = min(g[i][a[i]], g[i-1][j] + (j - a[i] >= x));
            }
        } else {
             rep(j,0,100) {
                rep(k,0,100) {
                    f[i][k] = max(f[i][k], f[i-1][j] + (j - k >= x));
                    g[i][k] = min(g[i][k], g[i-1][j] + (j - k >= x));
                }
            }
        }
    }
    int ans1 = -114514, ans2 = 114514;
    rep(j,0,100) {
        ans1 = max(ans1, f[n][j]);
        ans2 = min(ans2, g[n][j]);
    }
    cout << ans1 << ' ' << ans2 << endl;
}