Сложная логика dp

Question

Я пытаюсь решить вопрос динамического программирования на hackerearth. Даже после попытки моделирования логики с использованием ручки и бумаги я не могу понять решение (данное в editorial). Может кто-нибудь объяснить прокомментированные строки? Любая помощь будет принята с благодарностью. Я пытался понять это в течение 3 дней ...

#include<bits/stdc++.h> 
using namespace std; 
const int MAXN = 5e3+5; 
bool vis[MAXN]; 
int ar[MAXN]; 
int pre[MAXN]; 
vector<int> v; 
int dp[MAXN]; 
void sieve() { 
    v.push_back(2); 
    for(int i=3;i<MAXN;i+=2) if(!vis[i]) { 
     v.push_back(i); 
     for(int j=i*i;j<MAXN;j+=2*i) vis[j]=true; 
    } 
} 
int main() { 
    // freopen("TASK.in","r",stdin);  
    // freopen("TASK.out","w",stdout); 
    int n; 
    cin>>n; 
    assert(n<=5000); 
    for(int i=1;i<=n;i++) { 
     scanf("%d",&ar[i]); 
     assert(ar[i]<=100000); 
     pre[i]=pre[i-1]+ar[i]; 
    } 
    sieve(); 
    dp[0]=dp[1]=0; 
    for(int i=2;i<=n;i++) { 
     dp[i]=dp[i-1]; 
     for(int j=0;j<(int)v.size() and v[j]<=i;j++) { 
      int p=i-v[j]-1;//please explain this line 
      if(p==-1) dp[i]=max(dp[i],pre[i]); 
      else dp[i]=max(dp[i],dp[p]+pre[i]-pre[p+1]);// please explain this line 
     } 
    } 
    cout<<dp[n]<<endl; 
    return 0; 
} 

Answer 1

array pre Здесь стенды для префиксной суммы, vector v содержит простые числа ниже MAXN. Первая линия вы прокомментировали это
int p=i-v[j]-1;
Здесь v[j] является jth простого числа, начиная с 2, dp[i] лучшим возможным баллом для первых i проблем. Если вы решите v[j] количество последовательных проблем (от i и назад), вы останетесь с i - v[j] проблемами с самого начала. -1 исходит из того, что вы не можете решить проблему (v[j] - 1) th от i (если вы это сделаете, то вы решите v[j] + 1 последовательные проблемы, которые не являются первыми, поскольку v[j] является простым).

Вторая линия вы прокомментировали:
dp[i]=max(dp[i],dp[p]+pre[i]-pre[p+1]);
Это следует из выше, так как если вы решите v[j] проблемы с i (назад), вы получите pre[i]-pre[p+1] очков и добавить, что с dp[p] который является лучшим результатом вы уже получили для p. Например, если i = 10 и v[j] = 3 вы получаете dp[10] = max (dp[10],dp[6]+pre[10]-pre[7]), что и следовало ожидать.