Yutaka/ sushi variegato


#1

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

#2

Perdonatemi, si sono sminate tutte le tabulazioni


#3

Potresti linkare il testo del problema?


#4

https://training.olinfo.it/#/task/preoii_yutaka/statement