제출 #1212931

#	제출 시각	아이디	문제	언어	결과	실행 시간	메모리
1212931		minhpk	Lamps (JOI19_lamps)	C++20	0 / 100	18 ms	26008 KiB

lamp

#include <bits/stdc++.h>
using namespace std;

 // just to test algo from gpt to learn:)

// Chúng ta định nghĩa dp[i][mode][value]:
//   - i: đã xử lý xong prefix độ dài i (i từ 0 đến n).
//   - mode: loại thao tác hiện đang kéo dài đến vị trí i:
//       + mode = 0: đang trong (hoặc vừa kết thúc) một thao tác SET (gán toàn bộ về 0 hoặc gán toàn bộ về 1).
//       + mode = 1: đang trong (hoặc vừa kết thúc) một thao tác FLIP (đổi ngược bit).
//   - value: giá trị cuối cùng mà vị trí i đã có sau khi áp dụng thao tác:
//       + value = 0: bit tại vị trí i = 0.
//       + value = 1: bit tại vị trí i = 1.
//       + value = 2: tại vị trí i **không dùng thao tác nào** (tức A[i-1] đã tự khớp với B[i-1]).
//
// dp[i][mode][value] lưu số thao tác tối thiểu để biến A[0..i-1] → B[0..i-1] sao cho
// vị trí i (ký tự A[i-1]) cuối cùng là value (0/1/2) và đang ở trong mode (0 = SET, 1 = FLIP).
//
// Chú ý: dp có kích thước (n+1) x 2 x 3. Ta sẽ khởi dp[0][0][2] = 0, tất cả các trạng thái khác = một số lớn (n).

static const int INF = 1000000000;
int dp[1001001][2][3];

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    int n;
    string A, B;
    cin >> n >> A >> B;

    // Khởi tạo tất cả dp = INF (một giá trị rất lớn).
    for (int i = 0; i <= n; i++) {
        for (int mode = 0; mode < 2; mode++) {
            for (int value = 0; value < 3; value++) {
                dp[i][mode][value] = INF;
            }
        }
    }
    // Với i = 0 (prefix độ dài 0), không cần thao tác nào, đang
    // ở trạng thái “không thao tác” (mode = 0, value = 2).
    dp[0][0][2] = 0;

    // Bắt đầu tính dp từ i = 1..n.
    for (int i = 1; i <= n; i++) {
        // u là giá trị mong muốn tại vị trí i (tương ứng B[i-1]).
        int u = B[i-1] - '0';  // u ∈ {0,1}

        // ========== Xét các trường hợp cần phải tạo ra một thao tác tại i ==========
        // Tức là cuối cùng, vị trí i sẽ bị “bao phủ” bởi một thao tác (SET hoặc FLIP),
        // và kết quả tại i phải bằng u (0 hoặc 1).

        // 1) Khi tại i chúng ta dùng thao tác SET (mode = 0), cho ra bit = u.
        {
            int mode = 0;          // mode = 0 tương ứng SET
            int desiredValue = u;  // muốn cuối cùng giá trị tại i = u

            // (a) Bắt đầu một đoạn SET mới ngay tại vị trí i:
            //     Trạng thái trước (i-1) phải ở “không thao tác” ⇒ value_prev = 2, mode_prev = 0 (theo quy ước)
            //     Từ dp[i-1][mode_prev = 0][value_prev = 2] + 1 thao tác mới
            int prev_cost_if_start_new_set = dp[i-1][0][2] + 1;

            // (b) Chuyển từ một đoạn FLIP đang diễn ra tại i-1 (mode_prev = 1),
            //     sao cho lúc i-1 kết quả là (1 - u), rồi mở SET tại i để cho ra u.
            //     Khi chuyển sang SET (mode = 0), code gộp chi phí bằng +0.
            //     value_prev phải = (1 - u).
            int prev_cost_if_switch_from_flip_to_set = dp[i-1][1][1 - u] + 0;

            // (c) Kéo dài đoạn SET đã tồn tại đến i-1 (mode_prev = 0, value_prev = u),
            //     rồi kéo dài tiếp qua i ⇒ vẫn cho ra u, không cộng thêm chi phí.
            int prev_cost_if_extend_set = dp[i-1][0][u];

            int best_cost_for_set = min({
                prev_cost_if_start_new_set,
                prev_cost_if_switch_from_flip_to_set,
                prev_cost_if_extend_set
            });

            // Gán vào dp[i][0][u]
            dp[i][0][u] = best_cost_for_set;
        }

        // 2) Khi tại i chúng ta dùng thao tác FLIP (mode = 1), cho ra bit = u.
        {
            int mode = 1;          // mode = 1 tương ứng FLIP
            int desiredValue = u;  // muốn cuối cùng giá trị tại i = u

            // Để flip mà cuối cùng ra u, thì ngay trước khi flip,
            // giá trị cũ phải là (1 - u).

            // (a) Bắt đầu một đoạn FLIP mới tại i:
            //     Trạng thái trước đó phải “không thao tác” (mode_prev = 0, value_prev = 2).
            //     Khởi một đoạn FLIP ⇒ cộng thêm 1 thao tác.
            int prev_cost_if_start_new_flip = dp[i-1][0][2] + 1;

            // (b) Chuyển từ một đoạn SET đang diễn ra tại i-1 (mode_prev = 0), sao cho lúc i-1 kết quả là (1 - u),
            //     rồi mở FLIP tại i ⇒ để cho ra u. Khi chuyển sang FLIP ta cộng thêm +1 thao tác.
            int prev_cost_if_switch_from_set_to_flip = dp[i-1][0][1 - u] + 1;

            // (c) Kéo dài đoạn FLIP đang tồn tại đến i-1 (mode_prev = 1, value_prev = 1 - u),
            //     rồi tiếp tục flip tại i ⇒ sẽ cho ra (1 - (1 - u)) = u. Không cộng chi phí thêm.
            int prev_cost_if_extend_flip = dp[i-1][1][1 - u];

            int best_cost_for_flip = min({
                prev_cost_if_start_new_flip,
                prev_cost_if_switch_from_set_to_flip,
                prev_cost_if_extend_flip
            });

            // Gán vào dp[i][1][u]
            dp[i][1][u] = best_cost_for_flip;
        }

        // ========== Xử lý trường hợp không dùng thao tác tại i (value = 2) ==========
        // Chỉ được phép khi A[i-1] == B[i-1] (tức A[i-1] = u).

        if (A[i-1] == B[i-1]) {
            // Trường hợp cho dp[i][0][2] (mode = 0 nhưng value = 2
            //   ý nghĩa: ở vị trí i, ta không mở thao tác nào).
            //
            // Có thể xuất phát từ 3 khả năng:
            //   (1) Từ dp[i-1][0][2]: trước đó không thao tác, giờ vẫn không thao tác.
            //   (2) Từ dp[i-1][1][2]: trước đó đang “kết thúc một FLIP” mà FLIP cho đúng u,
            //       giờ ta tiếp tục giữ “không thao tác” (chứ không mở thêm gì).
            //   (3) Từ dp[i][0][u]: tức ta đã tính xong dp[i][0][u] ở trên (kết thúc một SET tại i),
            //       và giá trị tại i khi đó = u = A[i-1], vậy giờ “kết thúc” SET luôn,
            //       chuyển về “không thao tác” cũng không tốn thêm chi phí.
            int cost_case1 = dp[i-1][0][2];
            int cost_case2 = dp[i-1][1][2];
            int cost_case3 = dp[i][0][u];  // Kết thúc SET tại i ⇒ “không thao tác” tại i.

            dp[i][0][2] = min({ cost_case1, cost_case2, cost_case3 });

            // Trường hợp dp[i][1][2]: tức “kết thúc một FLIP” tại i mà FLIP đó cho đúng bit u.
            // → Nếu ta đã tính dp[i][1][u] ở trên (là chi phí tối thiểu để ở vị trí i vẫn
            // trong FLIP mà kết quả = u), thì kết thúc FLIP luôn sẽ chuyển value → 2.
            dp[i][1][2] = dp[i][1][u];
        }
        else {
            // Nếu A[i-1] != B[i-1], tức không thể “không thao tác” tại i.
            // Tuy nhiên code vẫn gán dp[i][0][2] = dp[i][0][u], vì đó tương đương “kết thúc SET”
            // tại i (nhưng chỉ đúng nếu SET thực ra cho ra u). Còn dp[i][1][2] tính riêng.
            //
            // – Với mode = 0, value = 2: ta chỉ có thể “kết thúc ngay SET tại i”
            //   nếu dp[i][0][u] đã có (SET cho ra u). Không thêm lựa chọn nào khác.
            dp[i][0][2] = dp[i][0][u];

            // – Với mode = 1, value = 2: nghĩa là “kết thúc FLIP” tại i
            //   sao cho bit tại i phải đúng = u. Ta có 3 khả năng:
            //   (1) Bắt đầu một FLIP mới ngay i: dp[i-1][0][2] + 1.
            //   (2) Từ dp[i-1][1][2]: giữ nguyên FLIP cũ và tiếp tục flip tại i (flip vẫn cho đúng u).
            //   (3) Từ dp[i][1][u]: đã tính xong dp[i][1][u] ở trên (mode=1, value=u), bây giờ kết
            //       thúc FLIP ⇒ value chuyển thành 2.
            int cost_new_flip = dp[i-1][0][2] + 1;
            int cost_extend_existing_flip = dp[i-1][1][2];
            int cost_end_flip_at_i = dp[i][1][u];

            dp[i][1][2] = min({ cost_new_flip, cost_extend_existing_flip, cost_end_flip_at_i });
        }
    }

    // Kết quả cuối cùng: lấy min giữa dp[n][0][2] và dp[n][1][2]
    // (cả hai đều là trạng thái “kết thúc chuỗi, không thao tác thêm").
    int answer = min(dp[n][0][2], dp[n][1][2]);
    cout << answer << "\n";
    return 0;
}

• Subtask 1: 0 / 6
• Subtask 2: 0 / 41
• Subtask 3: 0 / 4
• Subtask 4: 0 / 49