TREŚĆ ZADANIA
Mam problem z zadaniem. Pewnie można je rozwiązać znając się na grafach i usuwając pary tak, aby ich było jak najwięcej (nie znam się, więc to tylko przypuszczenie).
Moim pomysłem na zadanie było wykorzystanie programowania dynamicznego. Jeżeli pomysł jest dobry, to może popełniłem gdzieś błąd w kodzie, a jeżeli cały pomysł zły (lub częściowo), to proszę o wyjaśnienie dlaczego. Na podstawowych i nieskomplikowanych testach zwraca prawidłowe wyniki, jednak sprawdzarka mówi co innego :C
#include <bits/stdc++.h>
using namespace std;
int Solution(vector <pair <pair <int, int>, vector <int> > >& T, int& birds, int& guns) {
// 2 vectory, jeden dla aktualnego gołębie, drugi dla poprzedniego
vector <int> prev(birds + 1), actual(birds + 1);
// Opcjonalnie do wyświetlenia posortowanego vectora
for (int i = 0; i < T.size(); i++) {
for (int j = 0; j < T[i].second.size(); j++)
cout << T[i].second[j] << " ";
cout << "\n";
}
// Programowanie dynamiczne - spisujemy największą wartość lewo/góra, bądź wynik + 1
for (int i = 0; i < T.size(); i++) {
for (int j = 1; j <= birds; j++)
if (T[i].second[j])
actual[j] = prev[j - 1] + 1;
else
actual[j] = max(actual[j - 1], prev[j]);
prev = actual;
}
return actual.back();
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
int guns, birds;
cin >> guns >> birds;
// para do przechowania zakresu strzelania, cały przedział najbardziej w lewo, tj. największy gołąb ma najmniejszy numer
// oraz najmniejszy gołąb ma najmniejszy numer, tym problem jest mniej złożony
vector <pair <pair <int, int>, vector <int> > > T;
for (int i = 0; i < guns; i++) {
int aims, bird, maxBird = 0, minBird = INT_MAX;
cin >> aims;
vector <int> aim(birds + 1);
while (aims--) {
cin >> bird;
minBird = min(minBird, bird);
maxBird = max(maxBird, bird);
aim[bird]++;
}
T.push_back({{maxBird, minBird}, aim});
}
sort(T.begin(), T.end());
cout << Solution(T, birds, guns);
}
