Zadanie Cukiernia XXVIII OI

Question

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!

Answer 1

Mały hint: dp

Comments

ale zastanawia mnie kilka moich odpowiedzi typu: wczytano 1598 oczekiwano 0.

---

ooo znalazłem już test z WA:

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

biorę go na warsztat

---

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]

---

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!

---

wgl w najgorszych testach zużywa tylko około 1/20 czasu(pomijając fakt, że punkty spadają liniowo w dół od połowy)