【題解】Codeforces 1391D. 505

【題目敘述】http://codeforces.com/contest/1391/problem/D

#include <iostream>
#include <cstring>
using namespace std;
 
int n, m, g[1000005][3], dp[1000005][8];
string s;
 
int main() {
    cin >> n >> m;
    if (n >= 4 && m >= 4){
        for (int i = 0; i < n; i++){
            cin >> s;
        }
        cout << -1 << "\n";
        return 0;
    }
    if (n == 1 || m == 1){
        cout << 0 << "\n";
        return 0;
    }
    if (n < 4){
        for (int i = 0; i < n; i++){
            cin >> s;
            for (int j = 1; j <= m; j++){
                g[j][i] = s[j-1]-'0';
            }
        }
        swap(n, m);
    }
    else{
        for (int i = 1; i <= n; i++){
            cin >> s;
            for (int j = 0; j < m; j++){
                g[i][j] = s[j]-'0';
            }
        }
    }
    memset(dp, 0x3F, sizeof(dp));
    for (int i = 0; i < (1<<m); i++){
        dp[0][i] = 0;
    }
    for (int i = 1; i <= n; i++){
        for (int j = 0; j < (1<<m); j++){
            int cost = 0;
            for (int k = 0; k < m; k++){
                if (((j>>k)&1) != g[i][k]) cost++;
            }
            for (int k = 0; k < (1<<m); k++){
                int tmp = j^k;
                if (!((tmp^(tmp>>1))&1)) continue;
                else if (m == 3 && !(((tmp>>1)^(tmp>>2))&1)) continue;
                dp[i][j] = min(dp[i][j], dp[i-1][k]+cost);
            }
            //cout << i << " " << j << " " << dp[i][j] << "\n";
        }
        //cout << "\n";
    }
    int mn = 10000000;
    for (int i = 0; i < (1<<m); i++){
        mn = min(mn, dp[n][i]);
    }
    cout << mn << "\n";
}
分享本文 Share with friends