hdu 4925 Apple Tree(贪心)

题目链接：hdu 4925 Apple Tree

题目大意：给定一个N*M的网格，对于每个格子可以选择种树和施肥，默认一个苹果树收获1个苹果，在一个位置施肥的话，周围四个格子如果有种树，那么产量加倍。为最大产量。

解题思路：黑白格方法最优，可以通过公式求解2倍点，4倍点和8倍点的个数。特判1的情况。

#include <cstdio>
#include <cstring>
#include <algorithm>

using namespace std;

int N, M;

int solve () {
    if (N == 1 || M == 1) {
        if (N == 1 && M == 1)
            return 1;
        int n = max(N, M);
        int s = (n + 1) / 2;
        int t = (n&1 ? 2 : 1);
        return 2 * t + 4 * (s - t);
    }

    int s = (N * M + 1) / 2;
    int t = 1 + (N&1) + (M&1) + ((N&1)==(M&1));
    int k = N + M - 2 - t;
    return 4 * t + 8 * k + 16 * (s - k - t);
}

int main () {
    int cas;
    scanf("%d", &cas);
    while (cas--) {
        scanf("%d%d", &N, &M);
        printf("%d\n", solve());
    }
    return 0;
}