#include <fstream>
#include <iostream>
#include <vector>
#include <utility>
using namespace std;
int main()
{
ifstream in("input.txt");
int n; in >> n;
// vettore che tiene le soluzioni nel formato <numero missioni, fine ultima missione
vector<pair<int, int>> soluzioni;
int a, b; in >> a >> b;
soluzioni.push_back(make_pair(0, 0));
soluzioni.push_back(make_pair(1, soluzioni[0].second + a));
for (int i = 2; i < n + 1; ++i) {
in >> a >> b;
auto j = soluzioni.size();
auto sol2 = soluzioni[j - 2];
//cout << sol2.first << " " << sol2.second << "\n";
auto sol1 = soluzioni[j - 1];
//cout << sol1.first << " " << sol1.second << "\n\n";
// aggiunge la nuova missione solo se possibile entro la scadenza
if (sol1.second + a <= b) {
sol1.second = sol1.second + a;
++sol1.first;
}
if (sol2.second + a <= b) { // come sopra
sol2.second = sol2.second + a;
++sol2.first;
}
//cout << sol1.first << " " << sol2.first << " " << soluzioni[j - 1].first << "\n";
// controlla quale soluzione è la migliore contando l'ultima missione poi la aggiunge, ma solo se la nuova soluzione è migliore della precedente
if (sol1.first > sol2.first && sol1.first > soluzioni[j - 1].first) {
//cout << "sol 1\n";
soluzioni.push_back(sol1);
}
else if (sol1.first == sol2.first) { // se le soluzioni sono uguali è favorita quella che finisce prima
if (soluzioni[j - 1].second > sol1.second || sol2.second < soluzioni[j - 1].second) {
//cout << "sol == " << sol1.second << " " << sol2.second << "\n";
soluzioni.push_back(sol1.second <= sol2.second ? sol1 : sol2);
}
}
else {
//cout << "sol2\n";
if (sol2.first > soluzioni[j - 1].first)soluzioni.push_back(sol2);
}
}
//for (auto beg = soluzioni.begin(); beg != soluzioni.end(); ++beg) {
//cout << beg->first << " " << beg->second << "\n";
//}
ofstream out("output.txt");
out << (*(soluzioni.end() - 1)).first << endl;
out.close();
}
Ho implementato questa soluzione stile dynamic programming per Missioni ma non passa i test case 6, 7, 8.
Inizialmente credevo di aver individuato il problema in quanto non consideravo il caso in cui ci fossero una serie di missioni con la stessa scadenza ma durata minore una dopo l’altra e ho corretto il programma ma non li passa lo stesso.
Ora sarei sul punto di implementare un’ altra soluzione ma mi piacerebbe capire perchè non funziona questa.