Codice:
#include <bits/stdc++.h>
using namespace std;
#define pb push_back
#define nl '\n'
#define ll long long
const int mod = 1e9 + 7;
const int mxn = 1e6 + 100;
int taglia(int N, int V[]) {
ll dp[N+1];
ll pref[N+1];
memset(dp, 0, sizeof(dp));
memset(pref, 0, sizeof(pref));
dp[0] = 1;
pref[0] = 1;
vector<int> lastSeen(mxn, -1);
int lastD = 0;
for (int i = 1; i <= N; i++) {
// Devo confrontare questo con il massimo tra lastD e l'ultima istanza trovata di se' stesso
lastD = max(lastSeen[V[i-1]], lastD);
dp[i] = pref[i-1] - (lastD ? pref[lastD-1] : 0);
dp[i] %= mod;
pref[i] = pref[i-1] + dp[i];
pref[i] %= mod;
lastSeen[V[i-1]] = i;
}
return dp[N];
}
Credo che l’idea sia corretta. La spiego per chiarezza:
dp[i] = numero di modi di dividere l’array fino alla posizione i-1
Posso porre divisioni all’array in tutte le posizioni precedenti, fino alla ultima posizione in cui un piatto sarebbe ripetuto.
Uso prefix sum per velocizzare questa somma.
Eppure questo codice prende 53/100, qualcuno puo’ consigliarmi cosa c’e’ di sbagliato?
Grazie 