Pagini recente » Diferente pentru autumn-warmup-2007/solutii/runda-3 intre reviziile 53 si 43 | Diferente pentru preoni-2007/runda-4/solutii intre reviziile 7 si 34 | Istoria paginii runda/test_1/clasament | Diferente pentru preoni-2008/runda-1/solutii intre reviziile 2 si 33 | Diferente pentru warm-up-2019/solutii/shoturi intre reviziile 24 si 23
Nu exista diferente intre titluri.
Diferente intre continut:
Această soluţie presupune tehnica programării dinamice. Vom folosi matricea $dp[n][k]$, pentru care:
* $dp[i][j]$ = suma potenţelor tuturor amestecurilor posibile ingerând j -shoturi- păhărele din primele i -substanţe interzise- sucuri.
* $dp[i][j]$ = suma potenţelor tuturor amestecurilor posibile ingerând <tex>j</tex> -shoturi- păhărele din primele <tex>i</tex> -substanţe interzise- sucuri.
De aici deducem recurenţa: <tex>\displaystyle \ dp[i][j]=\sum_{x=0}^{j-1} dp[i-1][x]*(j-x)*hazard[i] + dp[i-1][j]</tex>
De ce? Pentru că, din cum am definit dinamica, $dp[i-1][x]$ = suma potenţelor tuturor amestecurilor posibile ingerând x păhărele din primele i-1 sucuri. Cum $dp[i][j]$ presupune ingerarea a <tex>j</tex> pahare $=>$ se vor ingera j-x pahare de tipul i
De ce? Pentru că, din cum am definit dinamica, $dp[i-1][x]$ = suma potenţelor tuturor amestecurilor posibile ingerând <tex>x</tex> păhărele din primele <tex>i-1</tex> sucuri
Nu exista diferente intre securitate.
Topicul de forum nu a fost schimbat.
