ho risolto questo problema con la ricorsione come presentato nell’editoriale il prolema è che l’editoriale presenta anche un altro modo per raggiungere la soluzione attraverso la programmazione dinamica e quest’ultimo non lo capisco.
Ecco il codice della soluzione con DP:
#include <iostream>
#include <vector>
#include <bitset>
int main() {
using namespace std;
unsigned N, T, M;
cin >> N >> T >> M;
vector<unsigned> hate(N);
for(unsigned i{}, a, b; i < M; ++i){
cin >> a >> b;
hate[--b] |= 1U << --a;
}
// possible_team[S] := The team with players in S does not have an incompatible pair
// O(2^N N^2/w) time
bitset<1024> possible_team;
for(unsigned i{}; i < 1U << N; ++i){
unsigned m{};
for(unsigned j{}; j < N; ++j)if(1U & (i >> j))m |= hate[j];
if(!(i & m))
possible_team[i] = true;
}
vector dp(1U << N, vector<unsigned>(T + 1));
dp.front().front() = 1;
for(unsigned i{}; i < 1U << N; ++i)
// brute-force over all possible teams that the remaining player with the minimum integer belongs
for(unsigned c{i + 1 | i}, j{c}; j < 1U << N; ++j |= c) //fino a qua ci sono
if(possible_team[j ^ i]) //queste ultime tre righe di codice non le capisco, perchè fa lo XOR tra j e i, non dovrebbe fare l'OR?
for(unsigned k{}; k < T; ++k)
dp[j][k + 1] += dp[i][k];
cout << dp.back().back() << endl;
return 0;
}
mi sono chiari i passaggi fino al momento della soluzione vera e propria