题解：CF283B Cow Program

a_small_penguin · 2025-04-23 14:50:29 · 题解

什么是 DP？我不知道，我只知道什么叫做暴力。

这道题是一道 DP 的板题，但我不善 DP，于是就用暴力淼过去了。

对于每个查询，就为从 1 跳过去的点多出的贡献再加上 1 的点值。

对于暴力的 dfs，传入一个二元组 (x, d)，代表当到了 x，该进行操作 d + 1 时的状态，返回值是到这个状态下多出的贡献。

直接爆搜是不能过的，所以我们应该使用记忆化搜索。

对于一些特判：

如果二元组 (x, d) 这个状态已经访问过了，且这个状态还没有返回值，那么就一定有环，返回 -\infty。

如果二元组 (x, d) 已经访问过且有值，那么直接返回值。

如果 x < 1 \text{或} n < x 那么就直接返回 0，因为到这里就结束，不会有多余的贡献。

如果 x = 1 那么就一定有环，返回 -\infty。

对于其余的情况

Code：

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

#define int long long
#define inf64 0x7fffffffffffffff

int n;
int a[200009];
int f[200009][2];
bool c[200009][2];

inline long long dfs(int x, int d) {
    if(x == 1) return -inf64;
    if(x < 1 || x > n) return 0;
    if(f[x][d]) return f[x][d];
    if(c[x][d]) return -inf64;

    if(d)
        c[x][d] = 1, f[x][d] = dfs(x - a[x], 0) + a[x];
    else
        c[x][d] = 1, f[x][d] = dfs(x + a[x], 1) + a[x];
    return f[x][d];
}

signed main() {

    ios::sync_with_stdio(false);
    cin.tie(0);
    cout.tie(0);

    cin >> n;
    for(int i = 2; i <= n; i++)
        cin >> a[i];
    for(int i = 2; i <= n; i++)
        f[i][1] = dfs(i, 1);
    for(int i = 2; i <= n; i++)
        if(f[i][1] < 0) cout << -1 << "\n";
        else cout << f[i][1] + i - 1 << "\n";

    return 0;

}