Submission #1117564

#	Time	Username	Problem	Language	Result	Execution time	Memory
1117564		Zero_OP	Lamps (JOI19_lamps)	C++14	100 / 100	46 ms	16472 KiB

lamp

#include <bits/stdc++.h>

using namespace std;

int call(int state, int op){
    if(op == 0) return state;
    if(op == 1) return 0;
    if(op == 2) return 1;
    assert(false);
}

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

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

    for(auto& c : A) c -= '0';
    for(auto& c : B) c -= '0';

    vector<array<int, 3>> dp(N + 1, {N, N, N});

    //0 : keep
    //1 : turn off
    //2 : turn on

    dp[0][0] = 0;
    for(int i = 1; i <= N; ++i){
        for(int pre = 0; pre < 3; ++pre){
            for(int cur = 0; cur < 3; ++cur){
                int need = dp[i - 1][pre] + (pre != cur && cur != 0);
                if((i == 1 || (call(A[i - 2], pre) == B[i - 2])) && call(A[i - 1], cur) != B[i - 1]){
                    ++need;
                }

                dp[i][cur] = min(dp[i][cur], need);
            }
        }
    }

    cout << min({dp[N][0], dp[N][1], dp[N][2]});

    return 0;
}

/*

Nhận xét 1 : Thực hiện trước tất cả các thao tác ON/OFF trước khi TOGGLE, chứng minh trực giác vì ON/OFF giống như xóa thông tin của cột trước khi thực hiện, còn TOGGLE là giữ lại thông tin đó theo các khác

Nhận xét 2 : Tồn tại cách giải tối ưu thỏa mãn : 
- Thực hiện tất cả thao tác ON/OFF trước khi TOGGLE
- Các đoạn thực hiện ON/OFF không chồng lên nhau
- Các đoạn thực hiện ON/OFF không liền kề nhau

*/

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