Problema Nunta – OJI 2002, Clasa a 11-a

Problema Nunta – OJI 2002, Clasa a 11-a

  • Dificultate:
  • Autor: Emanuela Cerchez
  • Online: PbInfo

Rezumat

Avem un șir de nn numere. La fiecare pas, putem alege două numere situate pe poziții consecutive și să le înlocuim cu modulul diferenței lor. Ne oprim după ce am rămas cu un singur număr. Să se determine toate valorile pe care le poate lua acesta. Elementele șirului dat sunt numere naturale cuprinse între 00 și 2020

Soluție

Aceasta este o problemă de programare dinamică foarte similară cu celebra parantezare optimă de matrice. Diferența constă în modul în care combinăm stările dp[i][k]\mathrm{dp}[i][k] și dp[k+1][j]\mathrm{dp}[k + 1][j] Notăm cu dp[i][j]\mathrm{dp}[i][j] mulțimea valorilor pe care le poate lua elementul la care este redusă secvența [i,j][i, j] Acest element este obținut înlocuind elementele la care sunt reduse două secvențe [i,k][i, k] și [k+1,j][k + 1, j] unde ik<ji \le k \lt j cu modulul diferenței lor. Așadar, pentru a calcula dp[i][j]\mathrm{dp}[i][j] luăm fiecare element xx din dp[i][k]\mathrm{dp}[i][k] fiecare element yy din dp[k+1][j]\mathrm{dp}[k + 1][j] și inserăm în dp[i][j]\mathrm{dp}[i][j] valoarea xy|x - y| Formal, recurența este:

dp[i][j]=ik<j{xyxdp[i][k],ydp[k+1][j]}\mathrm{dp}[i][j] = \bigcup_{i \le k \lt j} \{ |x - y| \mid x \in \mathrm{dp}[i][k], y \in \mathrm{dp}[k + 1][j] \}

Mai rămâne să alegem modalitatea de reprezentare a mulțimilor. Putem folosi set-uri din STL fără probleme, însă mai elegant și mai eficient ar fi să folosim bitmask-uri. Putem face asta deoarece atât valorile inițiale, cât și cele intermediare, sunt rezonabil de mici (maxim 2020 Astfel, fiecare stare a dinamicii va fi reprezentată printr-un întreg în care bitul xx va fi setat la 11 dacă și numai dacă valoarea xx apare în mulțimea dp[i][j]\mathrm{dp}[i][j] Complexitatea soluției este O(n3k2)O(n^3 k^2) unde kk este valoarea maximă din șirul dat, și anume 2020

Sursă C++

Problema Nunta
#include <bits/stdc++.h>
using namespace std;
ifstream fin("nunta.in");
ofstream fout("nunta.out");
int main() {
int n; fin >> n;
vector<vector<int>> dp(n + 1, vector<int>(n + 1));
for (int i = 1; i <= n; i++) {
int x; fin >> x;
dp[i][i] = (1 << x);
}
for (int len = 2; len <= n; len++)
for (int i = 1, j = len; j <= n; i++, j++)
for (int k = i; k < j; k++)
for (int x = 0; x <= 20; x++) if (dp[i][k] & (1 << x))
for (int y = 0; y <= 20; y++) if (dp[k + 1][j] & (1 << y))
dp[i][j] |= (1 << abs(x - y));
int ans = 0;
for (int x = 0; x <= 20; x++)
ans += (bool) (dp[1][n] & (1 << x));
fout << ans << '\n';
for (int x = 0; x <= 20; x++)
if (dp[1][n] & (1 << x))
fout << x << ' ';
fout << '\n';
return 0;
}

Dacă ai vreo nedumerire cu privire la problema Nunta, lasă un comentariu și te voi ajuta

Mulțumesc că ai citit acest articol.
Dacă vrei să susții blogul, poți cumpăra un abonament de 2$.

patreon

Lasă un comentariu!

0 comentarii