• Najnowsze pytania
  • Bez odpowiedzi
  • Zadaj pytanie
  • Kategorie
  • Tagi
  • Zdobyte punkty
  • Ekipa ninja
  • IRC
  • FAQ
  • Regulamin
  • Książki warte uwagi

question-closed Dlaczego moje rozwiązanie jest błędne? Programowanie dynamiczne

Object Storage Arubacloud
0 głosów
142 wizyt
pytanie zadane 27 kwietnia 2021 w Algorytmy przez wojtek_suchy Mądrala (6,880 p.)
zamknięte 27 kwietnia 2021 przez wojtek_suchy

Cześć!
Rozwiązuje takie zadanko: https://codeforces.com/contest/489/submission/114363891
Pomysł taki, dla każdego chłopca sprawdzamy każdą dziewczynę, jeśli mogą stworzyć parę to zaznaczamy że ta dziewczyna jest przydzielona do chłopca i oraz zwiększamy prawdobobne party tego chłopca. Zaznaczamy dziewczynę tylko wtedy gdy ona nie miała jeszcze żadnego partnera lub parnter z którym jest ma więcej niż 1 możliwość pary. Na koniec sprawdzamy który z chłopców ma więcej niż 0 możliwości pary.
Mój program daje zbyt małe wyniki, niestety nie mam dostępu do testu.
Kod:

#include <bits/stdc++.h>

using namespace std;

#define ll long long
#define ull unsigned long long

const ll INF = 1e9 + 7, MAXN = 100 + 7;
vector<int> a(MAXN), b(MAXN), poss(MAXN, 0), rep(MAXN, -1);

void solve(){
    int n, m;
    cin >> n;
    for (int i = 0; i < n; i++)
        cin >> a[i];
    cin >> m;
    for (int i = 0; i < m; i++)
        cin >> b[i];

    for (int i = 0; i < n; i++)
        for (int j = 0; j < m; j++)
            if (abs(a[i] - b[j]) <= 1)
                if (rep[j] == -1 || poss[rep[j]] > 1){
                    if (rep[j] != -1)
                        poss[rep[j]]--;
                    rep[j] = i;
                    poss[i]++;
                }

    int ans = 0;
    for (int i = 0; i < n; i++)
        ans += poss[i] > 0;
    cout << ans << "\n";
}

void testcases(){
    int t;
    cin >> t;
    while(t){
        solve();
        t--;
    }
}

int main(){
    ios::sync_with_stdio(0);
    cin.tie(nullptr); cout.tie(nullptr);
    //testcases();
    solve();
    return 0;
}

Mógłby ktoś pomóc mi zrozumieć dlaczego mój program nie działa poprawnie?

komentarz zamknięcia: Błąd w pomyśle

Podobne pytania

0 głosów
2 odpowiedzi 100 wizyt
0 głosów
0 odpowiedzi 238 wizyt
pytanie zadane 29 maja 2021 w Algorytmy przez wojtek_suchy Mądrala (6,880 p.)
0 głosów
2 odpowiedzi 284 wizyt
pytanie zadane 6 czerwca 2021 w HTML i CSS przez mowmiheniek Stary wyjadacz (11,900 p.)

92,568 zapytań

141,424 odpowiedzi

319,630 komentarzy

61,956 pasjonatów

Motyw:

Akcja Pajacyk

Pajacyk od wielu lat dożywia dzieci. Pomóż klikając w zielony brzuszek na stronie. Dziękujemy! ♡

Oto polecana książka warta uwagi.
Pełną listę książek znajdziesz tutaj.

Akademia Sekuraka

Kolejna edycja największej imprezy hakerskiej w Polsce, czyli Mega Sekurak Hacking Party odbędzie się już 20 maja 2024r. Z tej okazji mamy dla Was kod: pasjamshp - jeżeli wpiszecie go w koszyku, to wówczas otrzymacie 40% zniżki na bilet w wersji standard!

Więcej informacji na temat imprezy znajdziecie tutaj. Dziękujemy ekipie Sekuraka za taką fajną zniżkę dla wszystkich Pasjonatów!

Akademia Sekuraka

Niedawno wystartował dodruk tej świetnej, rozchwytywanej książki (około 940 stron). Mamy dla Was kod: pasja (wpiszcie go w koszyku), dzięki któremu otrzymujemy 10% zniżki - dziękujemy zaprzyjaźnionej ekipie Sekuraka za taki bonus dla Pasjonatów! Książka to pierwszy tom z serii o ITsec, który łagodnie wprowadzi w świat bezpieczeństwa IT każdą osobę - warto, polecamy!

...