CF1268B Domino for Young （黑白染色）

Problem - 1268B - Codeforces

给出一个不规则的网格。共 nn 列,每列有 a_iai​ 个格子。现在要将 1 \times 21×2 的骨牌不重叠的覆盖在网格上，求最多能放的骨牌数量。

网格满足条件 高度左到右递减。

题解：

比较经典的骨牌填棋盘问题。

有神仙结论就是假如黑白间隔染色后，那么染出来的东西就一定可以用1*2的骨牌填满。

那么考虑填上即可。

假如都一样高，那么直接横着放就行了；

如果有差，那么就竖着填上差的部分再横着放；

ps：听说还有网络流经典棋盘建模操作，但是不会啊，好像还会T得很惨。数据有点不友好。 

/*keep on going and never give up*/
#include<bits/stdc++.h>
using namespace std;
#define int long long
#define ll long long
#define db(x) cerr<<(#x)<<" "<<(x)<<" "<<endl;
#define endl "\n"
#define fast std::ios::sync_with_stdio(false);cin.tie(0);cout.tie(0);
const double E = exp(1);
const double PI = acos(-1.0);
const int mod=1e9+7; 
const int maxn=2e5+10;
int n,cnt[maxn];
signed main() {fastcin>>n;for(int i=1,m;i<=n;i++){cin>>m;cnt[0]+=m/2;cnt[1]+=m/2;cnt[i%2]+=m%2;}	cout<<min(cnt[0],cnt[1]);
}