Atenţie! Aceasta este o versiune veche a paginii, scrisă la 2015-02-22 10:37:34.
Revizia anterioară Revizia următoare
Revizia anterioară Revizia următoare
Soluţii ONIS 2015, Runda 1
- Lista de probleme
- Por Costel şi Azerah
- Por Costel şi Algoritmul
- Por Costel şi Bujor
- Por Costel şi Comisia de Cenzură
- Por Costel şi Cifrul
- Por Costel şi Invazia Extraterestră
- Por Costel şi Livada
- Por Costel şi Meciul
- Por Costel şi Perechile
- Por Costel şi Pinball
- Por Costel şi Semipalindroamele
Por Costel şi Azerah
Solutia cea mai la indemana la problema aceasta se bazeaza pe metoda programarii dinamice:
Calculam:
dp[i][0] = numarul de submultimi cu suma numerelor para cu cele N numeredp[i][1] = numarul de submultimi cu suma numerelor impara cu cele N numere
Cazul de baza:
dp[0][0] = 1 (submultimea vida)dp[0][1] = 0
Relatia de recurenta:
* Daca numarul v[i] este par:
** dp[i][0] = 2 * dp[i-1][1]
** dp[i][1] = 2 * dp[i-1][1]
* Daca numarul v[i] este impar:
**@dp[i]0 = dp[i]0 + dp[i]1@
**@dp[i]1 = dp[i]0 + dp[i]1@
Complexitate: 
