Ho problemi su alcuni subtask che non mi spiego. Ho anche implementato due volte usando due approcci diversi ma faccio comunque solo 78 punti… Il problema sui subtask in questione (6, 9, 11, 15, 17) è che il programma restituisce la soluzione +1 (infatti se provo ad aumentare di 1 la soluzione finale fa bene solo quei subtask) e questo mi fa pensare che mi sfugge qualche caso particolare ma non arrivo a capire quale… qui codice:
#include <bits/stdc++.h>
int N, max = 1;
std::vector<std::pair<int, int> > tessere;
std::vector<bool> preso;
int solve(int s, int p);
int main(void) {
std::ifstream in("input.txt");
std::ofstream ou("output.txt");
in >> N;
int t1, t2;
for(unsigned i = 0; i < N; ++i) {
in >> t1 >> t2;
tessere.push_back(std::make_pair(t1, t2));
preso.push_back(false);
}
// per ogni possibile tessera iniziale
for(int i = 0; i < tessere.size(); i++) {
preso[i] = true;
int gg = solve(i, 1);
preso[i] = false;
}
ou << max;
in.close();
ou.close();
return 0;
}
int solve(int s, int p) {
// p rappresenta il numero di tessere che ho concatenato fin' ora
if(p > max) max = p;
for(int i = 0; i < N; i++) {
// se non ho ancora preso quella tessera e quella tessara ha
// almeno una faccia in comune con la precedente (s)
if(!preso[i] && (tessere[s].first == tessere[i].first ||
tessere[s].first == tessere[i].second ||
tessere[s].second == tessere[i].first ||
tessere[s].second == tessere[i].second)) {
preso[i] = true;
solve(i, p+1);
preso[i] = false;
}
}
}