题目链接：http://codeforces.com/contest/284/problem/D
题意：给出n个数，奇数次操作x,y都加上a[x],偶数次操作y加上a[x],x减去a[x],走出了范围就结束。 问结束时的y值，如果无法结束，那么输出-1
题解：很显然可以用记忆化搜索来解决，可以设dp[i][j]（i=0表示偶数次操作以j为结尾的y值是多少，i=1表示奇数次操作以j为结尾的y值是多少）
在加一个辅助的vis[i][j]（i=0表示偶数次操作以j为结尾有没有取过，i=1表示奇数次操作以j为结尾有没有取过）
#include <iostream>
#include <cstring>
#include <string>
using namespace std;
const int M = 2e5 + 10;
typedef long long ll;
int a[M] , ans , n , cnt;
ll dp[2][M];
bool vis[2][M];
ll dfs(int pos , int flag) {
if(pos <= 0 || pos > n) return 0;
if(dp[flag][pos] != -1) return dp[flag][pos];
if(vis[flag][pos]) ans = 1;
if(ans) return -1;
vis[flag][pos] = true;
ll sum = 0;
if(flag == 1) {
sum += (a[pos] + dfs(pos + a[pos] , 0));
}
else {
sum += (a[pos] + dfs(pos - a[pos] , 1));
}
if(!ans)
dp[flag][pos] = sum;
return sum;
}
int main() {
scanf("%d" , &n);
for(int i = 2 ; i <= n ; i++) {
scanf("%d" , &a[i]);
}
ll gg;
memset(dp , -1 , sizeof(dp));
memset(vis , false , sizeof(vis));
for(int i = 1 ; i < n ; i++) {
ans = 0;
gg = dfs(i + 1 , 0);
if(ans) {
printf("-1\n");
}
else {
printf("%lld\n" , gg + (ll)i);
}
}
return 0;
}