又是大水题。
考虑连续两个元素对答案的贡献。
- ：一居室和二居室对答案的贡献均为 。（）
- ：一居室和二居室对答案的贡献均为 。（）
- ：一居室和二居室对答案的贡献均为 。（）
- ：一居室对答案的贡献为 ，二居室对答案的贡献为 。（）
因此可以发现只有（）时一居室和二居室答案不一样，因此考虑简单贪心。最小值就尽可能让 用二居室，最大值就尽可能让 用一居室。时间复杂度为 。
代码十分好写。
#pragma GCC optimize(3)
#include <bits/stdc++.h>
#define eb emplace_back
#define int long long
using namespace std;
const int N = 200100;
int f[N][22][2], a[N];
signed main() {
int n, m;
cin >> n >> m;
int c1 = 0, c2 = 0;
for (int i = 1; i <= n; ++i) {
string s;
cin >> s;
s = ' ' + s;
int ff = 0;
for (int j = 1; j <= m; ++j) {
if (s[j] == '1') {
++ff;
}
}
int gg = 0;
for (int j = 1; j < m; ++j) {
if (s[j] == '1' && s[j + 1] == '1') {
++j, ++gg;
}
}
int hh = 0;
for (int j = 1; j < m; ++j) {
if (!(s[j] == '1' && s[j + 1] == '1')) {
++j, ++hh;
}
}
c1 += ff - max(0ll, m / 4 - hh);
c2 += ff - min(m / 4, gg);
}
cout << c2 << ' ' << c1 << '\n';
return 0;
}
/*
*/
喜欢的话，留下你的评论吧～