icontofig | 发布于 2019-12-22 13:56:06 | 阅读量 393 | 思维题
发布于 2019-12-22 13:56:06 | 思维题

题目大意

给一个不完整的棋盘,每一列的方格数单调非升,问最多可以用多少个不重叠的1x2或者2x1的矩形覆盖棋盘(可以不完全覆盖)

题解

说实话思路比较巧妙

这种问题可以看成二分图匹配,相邻格子染色不同,假设分别染成黑白两种颜色,那么很明显想要用一个矩形覆盖,就必须要有一个黑格和一个白格匹配(两者相邻)。最大匹配数就是最终的答案。

但是这个数据范围过大,不能用匈牙利或者网络流解决。

注意到棋盘每一列的方格数是单调非升的,于是很明显只要先进行染色处理,然后从黑白格子中选出数量最少的那一种,其个数就是最大匹配数。

代码

#include <bits/stdc++.h>
using namespace std;
const int maxn = 3e5+5;
int n;
long long ans;
long long a[maxn];
long long black,white;
int main(){
    ios_base::sync_with_stdio(0);
    cin.tie(0);
    cin >> n;
    for(int i = 1;i <= n;++i){
        cin >> a[i];
        if(i & 1){
            black += a[i] / 2;
            white += (a[i] + 1) / 2;
        }
        else{
            black += (a[i] + 1) / 2;
            white += a[i] / 2;
        }
    }
    ans = min(black,white);
    cout << ans << endl;
    return 0;
}



内容更新于: 2019-12-22 13:56:14
链接地址: http://blog.leanote.com/post/icontofig/Codeforces-609-div1B-Domino-F

上一篇: HDU 2457 DNA Repair AC自动机 DP

下一篇: 并查集基础讲解

393 人读过
立即登录, 发表评论.
没有帐号? 立即注册
1 条评论
文档导航