https://codeforces.com/problemset/problem/1804/D
解题思路
每个楼层是独立的,考虑怎么解决一层就可以了。
求最大值就是尽量避免1和1合并,也就是尽量在不存在连续1的子序列中进行合并,如果还有需要合并的就只能用1和1合并。求最小值就是尽量合并1和1。由于只需要输出最大最小值,所以遍历序列用贪心求解就行了。
/* https://codeforces.com/contest/1804/problem/D */ #include <bits/stdc++.h> using namespace std; int main() { int n, m, pre, num[2], sum, tmp[2], cnt, Max, Min; while (scanf("%d %d", &n, &m) != EOF) { Max = Min = 0; for (int i = 0; i < n; i++) { pre = -1; num[0] = num[1] = 0; sum = tmp[0] = tmp[1] = 0; for (int j = 0; j < m; j++) { char c = getchar(); if (c == '\n') { j--; continue; } cnt = c == '0' ? 0 : 1; sum += cnt; if (num[0] == 0) { pre = cnt; num[0]++; } else { if (cnt == 0) { pre = cnt; num[0]++; } else { if (pre == 0) { pre = cnt; num[0]++; } else { pre = cnt; tmp[0] += num[0] / 2; num[0] = 1; } } } if (cnt == 0) { if (num[1] != 0) { tmp[1] += num[1]/2; num[1] = 0; } } else { num[1]++; } } if (num[0] != 0) { tmp[0] += num[0]/2; } if (num[1] != 0) { tmp[1] += num[1]/2; } Max += sum - (m/4 - min(m/4, tmp[0])); Min += sum - min(m/4, tmp[1]); } cout << Min << " " << Max << endl; } return 0; }
标签:tmp,pre,cnt,++,sum,codeforces,num,1804D,Accommodation From: https://www.cnblogs.com/fwjonair/p/17297601.html