记忆化搜索（dfs+字典）（dfs+剪枝）

解题思路: 一层循环线性遍历，vis用于去重，mp用于局部去重

注意事项: 目前 dotcpp 官方测评数据存在问题

参考代码:

错解（目前可通过 dotcpp 所有测试样例）

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long
using namespace  std;
const int MAXN=4e4+5;
int n,c[MAXN],ans;
unordered_map<int,bool> vis; //全局已走过的点
unordered_map<int,bool> mp; //本次搜索已走过的点
unordered_map<int,bool> valSet; //本次搜索已获得的c的集合
void dfs(int start){
//    cout<<start<<"\n";
    valSet[start]=true;
    mp[start]=true;
    vis[start]=true;
    
    int next=start+c[start];
    if(next <= n && mp.find(next) == mp.end()){// cout<<start<<"--"<<next<<"\n";
        dfs(next);
    }
    
    next=2*start;
    if(next <= n && mp.find(next) == mp.end()){// cout<<start<<"--"<<next<<"\n";
        dfs(next);
    }
}
signed main(){
    IOS;
    cin>>n;
    for(int i=1;i<=n;++i) cin>>c[i];
    
    for(int i=1;i<=n;++i){
        if(vis.find(i) == vis.end())
        {
            mp.clear();
            valSet.clear();
            dfs(i);
            ans=max(ans,(int )valSet.size());
        }
    }
    cout<<ans<<endl;
    return 0;
}

正解（目前无法通过 dotcpp 测试样例）

#include <bits/stdc++.h>
#define IOS ios::sync_with_stdio(0),cin.tie(0),cout.tie(0)
#define int long long
using namespace  std;
const int MAXN=4e4+5;
int n,c[MAXN],ans;

unordered_map<int,bool> vis; //全局已走过的点
unordered_map<int,bool> mp; //本次搜索已走过的点
unordered_map<int,bool> valSet; //本次搜索已获得的c的集合
void dfs(int start){
//    cout<<start<<"\n";
    valSet[c[start]]=true;
    mp[start]=true;
    vis[start]=true;
    
    int next=start+c[start];
    if(next <= n && mp.find(next) == mp.end()){// cout<<start<<"--"<<next<<"\n";
        dfs(next);
    }
    
    next=2*start;
    if(next <= n && mp.find(next) == mp.end()){// cout<<start<<"--"<<next<<"\n";
        dfs(next);
    }
}
signed main(){
    IOS;
    cin>>n;
    for(int i=1;i<=n;++i) cin>>c[i];
    
    for(int i=1;i<=n;++i){
        if(vis.find(i) == vis.end())
        {
            mp.clear();
            valSet.clear();
            dfs(i);
            ans=max(ans,(int )valSet.size());
        }
    }
    cout<<ans<<endl;
    return 0;
}