HDU 4925 Apple Tree：棋盤染色貪心最大化收獲

問題描述

n×m 果園。種樹格子收獲 1 果實；施肥格子使其四周相鄰格子的樹果實翻倍。每格只能種樹或施肥或空置。最大化總收獲。

核心洞見：棋盤染色 + 獨立集

相鄰格子不能同時種樹（否則無法同時受益於施肥）。最優策略：

1. 將格子按 (i+j)%2 分為黑白兩類（二分圖）。
2. 選擇一類全種樹，另一類全施肥（或空置）。
3. 每棵樹有 2~4 個相鄰施肥格，收獲翻倍次數 = 相鄰施肥格數。
4. 總收獲 = Σ (樹格) 2^{相鄰施肥格數}。

因對稱性，只需計算黑作樹/白作肥 和 白作樹/黑作肥 兩種情況，取最大值。

關鍵代碼 (C++)

int main() {
    int T; scanf("%d", &T);
    while (T--) {
        int n, m; scanf("%d%d", &n, &m);
        long long ans = 0;
        // 情況1: (i+j)%2==0 種樹，其他施肥
        long long sum1 = 0;
        for (int i=1;i<=n;++i)
            for (int j=1;j<=m;++j)
                if ((i+j)%2==0) {
                    int cnt = 0;
                    if (i>1) cnt++;
                    if (i1) cnt++;
                    if (j1) cnt++;
                    if (i1) cnt++;
                    if (j

複雜度分析

時間：O(T * n * m) — 雙重循環遍歷格子。
空間：O(1)。


關鍵點

交叉種樹：即棋盤染色，保證樹不相鄰，每棵樹周圍全是施肥格。
邊界處理：角落樹鄰接 2 格，邊緣 3 格，內部 4 格，收獲分別為 4, 8, 16。
長整型：1LL << cnt 防溢出，n,m≤100 時最大 10000 * 16 = 1.6e5 但更大數據需 long long。


總結
HDU 4925 是「棋盤染色 + 獨立集貪心」的經典應用。將「種樹/施肥」二元選擇映射為二分圖兩色，利用對稱性枚舉兩種染色方案取最大值，是解決網格博弈/優化問題的標準套路。