dpのロジックが混乱している

Question

hackerearthで動的プログラミングの問題を解決しようとしています。 ペンと紙を使用してロジックをシミュレートした後でも、ソリューションを理解することができません（editorialに記載）。 誰かがコメント行を説明できますか？どんな助けでも大歓迎です。私はここに... 3日間のためにそれを理解するためにarray preを

#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

をしようとしているvector vがMAXN以下の素数を含んで、プレフィックス合計を表します。あなたがコメントしている最初の行はdp[i]が最初i問題について可能な限り最高のスコアである、ここでv[j]
int p=i-v[j]-1;
2から始まるjth素数です。 v[j]連続した問題の数を解決すると（iから後方に行く）、最初からi - v[j]の問題が残っています。 -1は、i（後ろ向き）から(v[j] - 1) th問題を解決できないという事実から来ています（これを行うとの連続問題はv[j]が素数であるため素数ではありません）。あなたがコメントしている

2行目は：あなたがiからv[j]問題を解決した場合（後方）あなたはpre[i]-pre[p+1]のポイントを取得し、あなたがdp[p]ですでにpのために得られた最良の結果であることを追加しますので、
dp[i]=max(dp[i],dp[p]+pre[i]-pre[p+1]);
それは上記から。たとえば、i = 10とv[j] = 3の場合は、dp[10] = max (dp[10],dp[6]+pre[10]-pre[7])が得られます。