Buongiorno a tutti, mi sto arrovellando da qualche giorno su questo problema, e non sono riuscito ancora a trovare una soluzione. L’algoritmo che ho implementato tenta di utilizzare una sorta di dp, anche se la complessità dell’algoritmo nel caso più sfigato è qualcosa simile a N^2.
Qualcuno ha qualche dritta da darmi? Incollo qua sotto il codice:
typedef long long int ull;
ull mod=1000000007;
ull val[1000000];
int taglia(int N, int V[])
{
val[0]=1;
for(int a=1;a<N;a++){
val[a]=(val[a-1]*2)%mod;
for(int b=a-1;b>=0;b--){
if(V[a]==V[b]){
val[a]=0;
for(int c=b;c<a;c++){
val[a]=(val[a]+val[c])%mod;
}
break;
}
}
}
return (int)val[N-1];
}