Verwirrende Logik von dp

-3

Ich versuche, eine dynamische Programmierung Frage auf hackerearth zu lösen. Auch nach dem Versuch, die Logik mit Stift und Papier zu simulieren, kann ich die Lösung nicht verstehen (gegeben in der editorial). Kann jemand die kommentierten Zeilen erklären? Jede Hilfe würde sehr geschätzt werden. Ich habe es 3 Tage zu verstehen versucht, ...Verwirrende Logik von dp

#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; 
}

Quelle

2017-01-11 coder

@Josh Lee Ich habe den Teil hervorgehoben, der eine Erläuterung benötigt.Scheint, dass Sie nicht die gesamte Beschreibung gelesen haben, also entfernen Sie bitte den Griff – coder

Fragen sollten vernünftig in sich geschlossen sein; Ihre Frage ist ohne die Seiten absolut bedeutungslos. Was passiert, wenn diese Seiten (temporär oder permanent) ausfallen? Was passiert, wenn jemand anderes die gleiche Frage wie Sie hat, und versucht, Stack-Überlauf, um zu sehen zu suchen, wenn es bereits beantwortet wurde? Was passiert, wenn jemand eine eingeschränkte Netzwerkverbindung hat und nicht riskieren möchte, auf Ihre Links zu klicken? – ruakh

@ks 1322 scheint, die Menschen wie die Beantwortung dp Fragen – coder

Hier array pre steht für Präfixsumme, enthält vector v Primzahlen unter MAXN. Erste Zeile, die Sie kommentiert haben, ist
int p=i-v[j]-1;
Hier v[j] ist die jth Primzahl von 2 starten, dp[i] die bestmögliche Punktzahl erste i Probleme ist. Wenn Sie v[j] Anzahl der aufeinanderfolgenden Probleme lösen (von i und rückwärts gehen) Sie sind mit i - v[j] Probleme von Anfang an. -1 kommt von der Tatsache, dass Sie das (v[j] - 1) th Problem von i (rückwärts) nicht lösen können (wenn Sie das tun, haben Sie v[j] + 1 aufeinander folgende Probleme gelöst, die nicht prim ist, da v[j] prim ist).

Zweite Zeile Sie kommentiert haben:
dp[i]=max(dp[i],dp[p]+pre[i]-pre[p+1]);
Nach oben da, wenn Sie v[j] Probleme von i (rückwärts) lösen Sie pre[i]-pre[p+1] Punkte und Sie fügen hinzu, dass mit dp[p] die beste Ergebnis ist, dass Sie bereits für p erhalten. Zum Beispiel, wenn i = 10 und v[j] = 3 Sie bekommen dp[10] = max (dp[10],dp[6]+pre[10]-pre[7]) das ist, was Sie erwarten würden.

Quelle

2017-01-12 07:15:25 xashru

@ Xashru danke für solch eine schöne Erklärung Ich hatte Mühe, es von 3 Tagen zu verstehen, vielen Dank. hoffe ich bekomme meine Punkte zurück – coder

Verwirrende Logik von dp

Antwort

Verwandte Themen