题解：CF283B Cow Program

什么是 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

。

对于其余的情况

dfs(x, d) = \begin{cases} dfs(x + a_x, d) + a_x & d = 0 \\ dfs(x - a_x, d) + a_x & d = 1 \end{cases}

Code：

CPP

#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;

}

题解：CF283B Cow Program

文章操作

对于一些特判：

对于其余的情况

相关推荐

评论

题解：CF283B Cow Program