# Yutaka/ sushi variegato

**URL:** <https://forum.olinfo.it/t/yutaka-sushi-variegato/5787>\
**Category:** Aiuto\
**Created:** [23 Luglio 2019, 2:45pm UTC](https://forum.olinfo.it/t/yutaka-sushi-variegato/5787 "2019-07-23T14:45:43Z")\
**Posts on this page:** 4\
**Page:** 1

<div class="post-metadata">

**Author:** ![AlessioZeni](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/e8c25b/32.png) [@AlessioZeni](https://forum.olinfo.it/u/AlessioZeni)\
**Post date:** [23 Luglio 2019, 2:45pm UTC](https://forum.olinfo.it/t/yutaka-sushi-variegato/5787/1 "2019-07-23T14:45:43Z")

</div>

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:

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

```

---

<div class="post-metadata">

**Author:** ![AlessioZeni](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/e8c25b/32.png) [@AlessioZeni](https://forum.olinfo.it/u/AlessioZeni)\
**Post date:** [23 Luglio 2019, 2:46pm UTC](https://forum.olinfo.it/t/yutaka-sushi-variegato/5787/2 "2019-07-23T14:46:07Z")

</div>

Perdonatemi, si sono sminate tutte le tabulazioni

---

<div class="post-metadata">

**Author:** ![Domilanza2002](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/d/c37758/32.png) [@Domilanza2002](https://forum.olinfo.it/u/Domilanza2002)\
**Post date:** [23 Luglio 2019, 2:53pm UTC](https://forum.olinfo.it/t/yutaka-sushi-variegato/5787/3 "2019-07-23T14:53:18Z")

</div>

Potresti linkare il testo del problema?

---

<div class="post-metadata">

**Author:** ![AlessioZeni](https://forum.olinfo.it/letter_avatar_proxy/v4/letter/a/e8c25b/32.png) [@AlessioZeni](https://forum.olinfo.it/u/AlessioZeni)\
**Post date:** [24 Luglio 2019, 7:39am UTC](https://forum.olinfo.it/t/yutaka-sushi-variegato/5787/4 "2019-07-24T07:39:56Z")

</div>

[https://training.olinfo.it/#/task/preoii\_yutaka/statement](https://training.olinfo.it/#/task/preoii_yutaka/statement)