题目大意

​ 给一个图表，图表是一个直方图，nn 列的高度分别为a1,a2,…,an(a1≥a2≥a3....≥an)a1,a2,…,an(a1≥a2≥a3....≥an)，你有许多大小为 1×21×2 的多米诺骨牌(可以旋转)，不重叠最多可以放置多少个呢?

分析

考虑对原图进行黑白染色

​ 题意

那么 res = min(black,white)res \ =\ min (black,white)

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
signed main()
{
    int n;cin>>n;
    vector<int> a(n+2,0);
    int w = 0,b=0;
    for(int i = 1;i <= n;i++){
        cin >> a[i];
        if(i&1){
            b += a[i]/2;
            w += a[i] - a[i]/2;
        }
        else{
            w += a[i]/2;
            b += a[i] - a[i]/2;
        }
    }
    cout << min(w,b) << endl;
    return 0;
}