[Codeforces][Round #693][Div.3] C : Long Jumps (C++)

https://codeforces.com/contest/1472/problem/C

Problem - C - Codeforces

 

[난이도] Div.3
[유형] DP

[풀이]
DP(i) (1<=i<=N) : index i를 선택했을 얻을 수 있는 점수.
점화식 : DP(i) = A[i] + DP(i+A[i])

 

#include <cstdio>
#include <algorithm>
#include <cstring>
using namespace std;
int tc,N,a[200001],dp[200001];
int sol(int n){
    if(n > N) return 0;
    int& ret = dp[n];
    if(ret!=-1) return ret;
    ret = a[n]+sol(n+a[n]);
    return ret;
}
int main(){
    scanf("%d",&tc);
    while(tc--){
        scanf("%d",&N);
        for(int i=1;i<=N;i++) scanf("%d",&a[i]);
        memset(dp,-1,sizeof(dp));
        int ans = 0;
        for(int i=1;i<=N;i++) ans = max(ans,sol(i));
        printf("%d\n",ans);
    }
}

 

https://github.com/has2/Problem-Solving/blob/master/codeforces/Round693-Div.3/C.cpp