HDU4925-Apple Tree

HDU4925-Apple Tree

題意：n*m網格中種蘋果，每個網格要麼施肥，要麼種一個蘋果，每個種蘋果的格子，如果它的上下左右有各自有施肥的話，每有一個，蘋果數量*2，求怎麼種使得蘋果數量最多。

思路：交叉種植，即黑白染色法可得到最優解。注意特判當n=m=1時的情況。

#include 
#include 
#include 
#include 

using namespace std;

const int MAXN = 105;

int n, m;
int g[MAXN][MAXN];

int deal(int x, int y) {
    int sum = 1;
    if (g[x][y - 1] == 1)
        sum *= 2;
    if (g[x][y + 1] == 1)
        sum *= 2;
    if (g[x - 1][y] == 1)
        sum *= 2;
    if (g[x + 1][y] == 1)
        sum *= 2;
    return sum;
}

int main() {
    int cas;
    scanf("%d", &cas);
    while (cas--) {
        scanf("%d%d", &n, &m);         
        if (n == 1 && m == 1) {
            printf("1\n"); 
            continue; 
        }
        memset(g, 0, sizeof(g));
        int flag = 1;
        if (m % 2 == 1) {
            for (int i = 1; i <= n; i++) 
                for (int j = 1; j <= m; j++) {
                    g[i][j] = flag; 
                    flag = -flag; 
                } 
        }
        else {
            for (int i = 1; i <= n; i++) { 
                for (int j = 1; j <= m; j++) {
                    g[i][j] = flag; 
                    flag = -flag; 
                }
                flag = -flag;
            }
        }

        long long ans = 0;
        for (int i = 1; i <= n; i++)
            for (int j = 1; j <= m; j++) 
                if (g[i][j] == -1)
                    ans += deal(i, j); 

        printf("%lld\n", ans);   
    }
    return 0;
}