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

Zadanie Cukiernia XXVIII OI

Object Storage Arubacloud
0 głosów
654 wizyt
pytanie zadane 1 maja 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Mam problem z takim zadaniem: https://szkopul.edu.pl/problemset/problem/rr3lU0T8pNn2mAbL07wBTZT3/site/?key=statement

Napisałem bruta w O(N^3), sprawdzając każdą trójkę i,j,k (zakładam, że na polu i jest pierwszy rodzaj wypieku, na j drugi rodzaj, a na k trzeci rodzaj wypieku), napewno da się to do O(N^2) przyśpieszyć sprawdzając każde dwójki, ale nie wiem co dalej.

Bardzo prosiłbym o jakiegoś hint-a, ale nie jakiegoś wielkiego, bo domyślam się, że to zadanie nie jest jakieś kosmicznie trudne.

Z góry dziękuję za pomoc i poświęcony czas!

1 odpowiedź

+1 głos
odpowiedź 1 maja 2023 przez Whistleroosh Maniak (56,980 p.)
wybrane 2 maja 2023 przez pasjonat_algorytmiki
 
Najlepsza
Mały hint: dp
komentarz 2 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Jednowymiarowe?
1
komentarz 2 maja 2023 przez Whistleroosh Maniak (56,980 p.)
dwuwymiarowe
komentarz 2 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
A jakby jakoś zrobić dp[i][mask], gdzie maska to jakaś maska bitowa 3 rodzajów wypieków?
komentarz 2 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
To wygląda jakby miało potencjał
komentarz 2 maja 2023 przez Whistleroosh Maniak (56,980 p.)
Brzmi dobrze
komentarz 2 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Mam lekki problem jak to policzyc, bo jeśli mam jakąś maskę i na danej pozycji jest zgaszony bit, to zaświecenie go to biorę łatwo dp do porównania, ale co jak mam jakąś maskę i na danej pozycji jest zapalony bit, a ja chce też go wziąć zapalonego
komentarz 2 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
Wait chyba mam
komentarz 2 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Napisałem tego dp i dostaję 52pkt, w 7 testach daje WA, trochę za duże wyniki, mam nadzieję, że to błąd w implementacji, a nie w pomyśle....

kod:

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

int n = 0;
ll INF = 1e18+20;
vector<ll> A;
vector<ll> B;
vector<ll> C;
vector<ll> min_sum;
vector<vector<ll>> dp;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    A.assign(n,-1);
    B.assign(n,-1);
    C.assign(n,-1);
    for (int i = 0; i < n; ++i)
        cin >> A[i] >> B[i] >> C[i];

    min_sum.assign(n,-1);
    for (int i = 0; i < n; ++i)
        min_sum[i] = min(A[i] + B[i], min(A[i] + C[i], B[i] + C[i]));

    dp.assign(n,{});
    for (int i = 0; i < n; ++i)
        dp[i].assign(8,INF);

    dp[0][0] = min_sum[0];
    dp[0][1] = A[0] + B[0];
    dp[0][2] = A[0] + C[0];
    dp[0][4] = B[0] + C[0];

    for (int i = 0; i < n-1; ++i)
    {
        for (int j = 0; j < 8; ++j)
            dp[i+1][j] = dp[i][j] + min_sum[i+1];
        for (int j = 0; j < 8; ++j)
        {
            auto b = (4 & j);
            if (!b)
            {
                int mask = j + 4;
                dp[i+1][mask] = min(dp[i+1][mask],dp[i][j] + B[i+1] + C[i+1]);
            }
            b = (2 & j);
            if (!b)
            {
                int mask = j + 2;
                dp[i+1][mask] = min(dp[i+1][mask],dp[i][j] + A[i+1] + C[i+1]);
            }
            b = (1 & j);
            if (!b)
            {
                int mask = j + 1;
                dp[i+1][mask] = min(dp[i+1][mask],dp[i][j] + A[i+1] + B[i+1]);
            }
        }
    }

    cout << dp[n-1][7] << '\n';

    return 0;
}

 

komentarz 2 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
ale zastanawia mnie kilka moich odpowiedzi typu: wczytano 1598 oczekiwano 0.
komentarz 2 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

ooo znalazłem już test z WA:

4
0 0 2
0 3 0
0 0 10
0 5 0

biorę go na warsztat

komentarz 2 maja 2023 przez Whistleroosh Maniak (56,980 p.)
Nie wczytywałem się za bardzo w kod, ale jeśli to działa podobnie jak u mnie to zastanów się czy na pewno wynikiem jest dp[n-1][7]
komentarz 2 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)

Tak dokładnie tu był błąd, problem był, gdy w jakimś wierszu(rodzaju rogalika) były same zera i ja dodwałem 2^i, a powinienem nie dodawać. Weszło na 100pkt, kod:

#include <iostream>
#include <vector>

using namespace std;
typedef long long ll;

int n = 0, max_A = 0, max_B = 0, max_C = 0;
ll INF = 1e18+20;
vector<int> A;
vector<int> B;
vector<int> C;
vector<int> min_sum;
vector<vector<ll>> dp;

int main()
{
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n;

    A.assign(n,-1);
    B.assign(n,-1);
    C.assign(n,-1);
    for (int i = 0; i < n; ++i)
        cin >> A[i] >> B[i] >> C[i];

    for (int i = 0; i < n; ++i)
    {
        max_A = max(max_A,A[i]), max_B = max(max_B,B[i]), max_C = max(max_C,C[i]);
    }

    min_sum.assign(n,-1);
    for (int i = 0; i < n; ++i)
        min_sum[i] = min(A[i] + B[i], min(A[i] + C[i], B[i] + C[i]));

    dp.assign(n,{});
    for (int i = 0; i < n; ++i)
        dp[i].assign(8,INF);

    dp[0][0] = min_sum[0];
    dp[0][1] = A[0] + B[0];
    dp[0][2] = A[0] + C[0];
    dp[0][4] = B[0] + C[0];

    for (int i = 0; i < n-1; ++i)
    {
        for (int j = 0; j < 8; ++j)
            dp[i+1][j] = dp[i][j] + min_sum[i+1];
        for (int j = 0; j < 8; ++j)
        {
            int b = (4 & j);
            if (b == 0)
            {
                int mask = j + 4;
                dp[i+1][mask] = min(dp[i+1][mask],dp[i][j] + B[i+1] + C[i+1]);
            }
            b = (2 & j);
            if (b == 0)
            {
                int mask = j + 2;
                dp[i+1][mask] = min(dp[i+1][mask],dp[i][j] + A[i+1] + C[i+1]);
            }
            b = (1 & j);
            if (b == 0)
            {
                int mask = j + 1;
                dp[i+1][mask] = min(dp[i+1][mask],dp[i][j] + A[i+1] + B[i+1]);
            }
        }
    }

    int sum = 0;
    if (max_A > 0)
        sum += 4;
    if (max_B > 0)
        sum += 2;
    if (max_C > 0)
        sum++;

    cout << dp[n-1][sum] << '\n';

    return 0;
}

Bardzo fajne zadanko na dp z maskami bitowymi, wgl warte podkreślenia, jest, że ten pomysł działa, jak są więcej niż 3 rodzaje wypieków, poprostu ma O(N * 2^liczba_wypiekow). Dzięki!

komentarz 2 maja 2023 przez pasjonat_algorytmiki Pasjonat (19,540 p.)
wgl w najgorszych testach zużywa tylko około 1/20 czasu(pomijając fakt, że punkty spadają liniowo w dół od połowy)

Podobne pytania

0 głosów
1 odpowiedź 133 wizyt
0 głosów
1 odpowiedź 569 wizyt
pytanie zadane 1 maja 2023 w Algorytmy przez pasjonat_algorytmiki Pasjonat (19,540 p.)

92,759 zapytań

141,682 odpowiedzi

320,458 komentarzy

62,104 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

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!

...