【正经题解】调皮的草原黄鼠

#include<bits/stdc++.h>
#define int long long
using namespace std;

const int MAX_N = 1005;

int dp[MAX_N][MAX_N];  // dp数组用于保存状态信息
int n, maxHole;  // n表示鼠洞的数量，maxHole表示最大鼠洞号

signed main() {
    cin >> n;
    for (int i = 1; i <= n; i++) {
        int hole;
        cin >> hole;
        dp[i][hole] = 1;  // 初始化dp数组，表示第i秒时第hole号鼠洞有鼠出现
        maxHole = max(maxHole, hole);  // 更新最大鼠洞号
    }

    // 从后往前遍历，计算每一秒在每个鼠洞位置能够抓到的最大鼠的数量
    for (int i = n - 1; i >= 1; i--) {
        for (int j = 1; j <= n; j++) {
            dp[i][j] += max(dp[i + 1][j], max(dp[i + 1][j - 1], dp[i + 1][j + 1]));
        }
    }

    int maxCatch = 0;  // 记录最多能抓到的鼠数量
    for (int i = 1; i <= n; i++) {
        maxCatch = max(maxCatch, dp[1][i]);
    }

    cout << maxCatch;  // 输出最多能抓到的鼠数量

    return 0;
}