제출 #1150995

#제출 시각아이디문제언어결과실행 시간메모리
1150995weakweakweakLamps (JOI19_lamps)C++20
0 / 100
12 ms19692 KiB
#include <bits/stdc++.h>
using namespace std;

int n;
string a, b;
int dp[2100][2100] = {0};

int main() {
    ios_base::sync_with_stdio(false); cin.tie(0);
    cin >> n >> a >> b;
    for (char &c : a) c -= '0';
    for (char &c : b) c -= '0';
    a = "$"+a, b = "$"+b;
    memset(dp, 63, sizeof(dp));
    dp[0][0] = 0;

    for (int i = 1; i <= n; i++) {
        for (int j = 0; j <= n; j++) {
            if (a[i] != b[i]) {
                if (j & 1) dp[i][j] = min(dp[i][j], dp[i-1][j]);
                dp[i][j+1] = min(dp[i][j+1], dp[i-1][j]+1);
                if (j > 0) dp[i][j-1] = min(dp[i][j-1], dp[i-1][j]);    
            }
            if (a[i] == b[i]) {
                if (j % 2 == 0) dp[i][j] = min(dp[i][j], dp[i-1][j]);
                dp[i][j+1] = min(dp[i][j+1], dp[i-1][j]+1);
                if (j > 0) dp[i][j-1] = min(dp[i][j-1], dp[i-1][j]);
            }
            if (b[i] == 0) {
                for (int k = i; k <= n and b[k] == 0; k++) dp[k][j] = min(dp[k][j], dp[i-1][j]+1);
            }
            if (b[i] == 1) {
                for (int k = i; k <= n and b[k] == 1; k++) dp[k][j] = min(dp[k][j], dp[i-1][j]+1);
            }
        }
    }

    int ans = INT_MAX;
    for (int i = 0; i <= n; i++) ans = min(ans, dp[n][i]);
    cout << ans << '\n';
}
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...
#Verdict Execution timeMemoryGrader output
Fetching results...