Problema Nunta – OJI 2002, Clasa a 11-a
- Dificultate:
- Autor: Emanuela Cerchez
- Online: PbInfo
Rezumat
Avem un șir de 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 și
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 și Notăm cu mulțimea valorilor pe care le poate lua elementul la care este redusă secvența Acest element este obținut înlocuind elementele la care sunt reduse două secvențe și unde cu modulul diferenței lor. Așadar, pentru a calcula luăm fiecare element din fiecare element din și inserăm în valoarea Formal, recurența este:
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 Astfel, fiecare stare a dinamicii va fi reprezentată printr-un întreg în care bitul va fi setat la dacă și numai dacă valoarea apare în mulțimea Complexitatea soluției este unde este valoarea maximă din șirul dat, și anume
Sursă C++
#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