[数据结构与算法]记忆化搜索

/*********
Author Smile
其实还是不太懂
还有就是
注：以后写递归千万注意全局变量还是局部变量，真的很重要
一般都是局部变量，看情况
本题是通过记录每一个x 对应的 y 值来减少时间的，因为
a[1] 这个点只可能会执行一次，所以可以用vis数组记录到底，最后直接输出答案
想想清楚也还好，虽然想了很久  
哭了 
https://vjudge.csgrandeur.cn/contest/477341#problem/D
**********/ 
#include <iostream>
#include <cstring>

using namespace std;
typedef long long ll;
const ll N = 2e5 + 10;
ll n;
ll a[N];
ll vis[N][2];
ll dp[N][2];

void dfs(int x, int j)
{
	if (vis[x][j])
		return ;
	vis[x][j] = 1;
	int y;
	if (j == 0)
		y = x - a[x];
	else 
		y = x + a[x];	
	if (y <= 0 || y > n)
		dp[x][j] = a[x];
	else
	{
		dfs(y, j ^ 1);
		if (dp[y][j ^ 1] != -1)
			dp[x][j] = dp[y][j ^ 1] + a[x];
	}				
}

int main()
{
	ios::sync_with_stdio(false);
	cin.tie(0), cout.tie(0);
	cin >> n;
	memset(dp, -1, sizeof dp);
	for (int i = 2; i <= n; ++i)
		cin >> a[i];
	for (int i = 2; i <= n; ++i)
	{
		dfs(i, 0);
	}	
	for (int i = 2; i <= n; ++i)
	{
		if (dp[i][0] != -1)
			dp[i][0] += i - 1;
		cout << dp[i][0] << endl;	
	}
	return 0;
}

当想要节省程序时间时可以考虑这一方面。