問題描述

小明正在和朋友們玩跳石頭的小游戲，一共有?n?塊石頭按 1 到?n?順序排成一排，第?i?塊石頭上寫有正整數權值?ci??。

如果某一時刻小明在第?j?塊石頭，那么他可以選擇跳向第?j+cj??塊石頭 （前提?j+cj≤n ）或者跳向第?2j?塊石頭（前提?2j≤n），沒有可跳躍的目標時游戲結束。

假如小明選擇從第?x?塊石頭開始跳躍，如果某塊石頭有可能被小明經過 （＂經過＂指存在某一時刻小明在這個石頭處），則將這塊石頭的權值納入得分集合?Sx??，那么小明從第?x?塊石頭開始跳躍的得分為?∣Sx∣。

比如如果小明從第?x?塊石頭出發，所有可能經過的石頭上的權值分別為?5,3,5,2,3 ，那么?Sx=5,3,2 得分為?∣Sx∣=3 。小明可以任選一塊石頭開始跳躍，請求出小明最多能獲得的分數。

輸入格式

輸入共?2?行。

第一行為一個正整數?n。

第二行為?n?個由空格分開的正整數?c1,c2,…,cn?。

輸出格式

輸出共 1 行，一個整數表示答案。

樣例輸入

5
4 3 5 2 1

樣例輸出

4

樣例說明

從第一塊石頭出發得分最多，路徑有以下幾種：

1. 1 號?→5 號：選擇從 1 號跳到?1+c1=5 號。
2. 1 號?→2?號?→5?號：第一次選擇從 1 號跳到?2×1=2 號，第二次選擇從 2 號跳到?2+c2=5??號。
3. 1 號?→2?號?→4?號：第一次選擇從 1 號跳到?2×1=2 號，第二次選擇從 2 號跳到?2×2=4 號

所以所有可能經過的石頭的權值的集合為 S1?={c1?,c2?,c4?,c5?}={4,3,2,1}?，得分為?∣S1∣=4。

評測用例規模與約定

對于?20% 的評測用例，保證 n≤20?。

對于?100% 的評測用例，保證?n≤40000,ci≤n 。

?

dfs 遍歷每一個石頭作為起點

用 set 記錄經過的石頭的權值

set 最多的元素數量即為答案

#include<iostream>
#include<algorithm>
#include<set>
using namespace std;int n;
const int N = 4e4+10;
int a[N];
set<int> s;
int ans;  //得分：所有可能經過的石頭上的不同權值的數量//x：當前石頭的編號 
void dfs(int x)
{if(x>n){int cnt = s.size();ans = max(cnt, ans);return;}s.insert(a[x]);  //記錄經過的所有石頭的權值//“跳向第 2j 塊石頭” dfs(2 * x);//“跳向第 j+cj 塊石頭” dfs(x + a[x]);
}int main()
{cin>>n;for(int i=1; i<=n; ++i) cin>>a[i];//遍歷每一塊石頭，選擇第 i 個石頭作為起點 for(int i=1; i<=n; ++i){dfs(i);  s.clear();}cout<<ans; return 0;
}