T16:拯救莫莉斯

1）题目意思

给你一个 n×m 的城市网格，每个格子 (i,j) 建一个油库要花 F[i][j] 的钱。

建完后要保证每个城市满足下面之一：

• 自己有油库
• 或者与某个有油库的城市相邻（上下左右相邻）

要求输出一组最优方案的：

1. 油库个数最少（在“总代价最小”的前提下）
2. 方案总代价最小（最主要目标）

也就是：先最小化总代价，若总代价相同再最小化油库数量。

数据范围：n*m<=50 且 m<=n，因此 m 最大不会超过 7（否则 8*8>50），可以做按行状态压缩 DP。

---

2）思路解析（按行状态压缩 DP）

关键观察

每个格子是否被覆盖，只与它自己和上下左右有关。按“行”处理时，第 i 行能否被覆盖，取决于：

• 第 i-1 行哪些列有油库（prev 掩码）
• 第 i 行哪些列有油库（cur 掩码）
• 第 i+1 行哪些列有油库（nxt 掩码）

因为：

• 上下覆盖看同列（prev/nxt 的同一位）
• 左右覆盖看同一行相邻列（cur 的相邻位）
• 自己覆盖看 cur 的本位

状态表示

用一个二进制数 mask 表示一行哪些列建油库（m<=7，所以 mask 最大 127）。

定义 DP：

• dp[i][prev][cur] 表示：已经决定到第 i 行（也就是第 1..i 行的建库情况都确定），并且保证 第 1..i-1 行都已经被覆盖。

  其中第 i-1 行的建库情况为 prev，第 i 行的建库情况为 cur。

  DP 存两件事：总代价 和 油库数量（用于相同总代价时比较）。

转移

枚举下一行 nxt（第 i+1 行的建库掩码），检查第 i 行是否被覆盖：

• 如果第 i 行在 (prev,cur,nxt) 的共同作用下能全覆盖，则可以转移：
  • dp[i+1][cur][nxt] = min( dp[i+1][cur][nxt], dp[i][prev][cur] + 行(i+1,nxt)的代价与数量 )

这里“min”按题意比较：

1. 代价小优先
2. 代价相同则油库少优先

初始化与收尾

• 第 0 行不存在，视作 prev=0
• 初始化：枚举第 1 行 cur，dp[1][0][cur] = 第1行cur的花费/数量
• 最后一行 n 需要被覆盖，因此在结束时令 nxt=0（第 n+1 行不存在）检查第 n 行覆盖即可。

复杂度

状态数大约是 n * 2^m * 2^m，每个状态枚举 nxt 再检查覆盖，m<=7 很稳能过。

---

3）代码

#include <bits/stdc++.h>
using namespace std;

const long long INF=(1LL<<62);                           // 定义无穷大

struct Node{                                              // 记录一个方案的指标
    long long cost;                                       // 总花费
    int cnt;                                              // 油库数量
};

bool better(const Node&a,const Node&b){                   // 比较两个方案谁更优
    if(a.cost!=b.cost)return a.cost<b.cost;               // 先比花费：小的优先
    return a.cnt<b.cnt;                                   // 花费相同再比数量：少的优先
}

int n,m;                                                  // 网格大小 n 行 m 列
long long F[55][8];                                       // 建库代价，m<=7 所以列开到 8（1-based）
Node dp[55][1<<7][1<<7];                                  // dp[i][prev][cur] 的最优方案

Node rowCost(int row,int mask){                           // 计算第 row 行按 mask 建库的花费与数量
    Node res;                                             // 定义返回值
    res.cost=0;                                           // 初始花费为 0
    res.cnt=0;                                            // 初始数量为 0
    for(int j=0;j<m;j++){                                 // 枚举列 j（0..m-1）
        if(mask&(1<<j)){                                  // 如果该列要建库
            res.cost+=F[row][j+1];                        // 累加该格子的建库代价（数组列是 1-based）
            res.cnt+=1;                                   // 油库数量 +1
        }
    }
    return res;                                           // 返回计算结果
}

bool rowCovered(int i,int prev,int cur,int nxt){           // 判断第 i 行是否被覆盖
    for(int j=0;j<m;j++){                                 // 枚举第 i 行每个格子 (i,j)
        bool ok=false;                                    // 标记该格子是否被覆盖
        if(cur&(1<<j))ok=true;                             // 自己有油库则覆盖
        if(j-1>=0&&(cur&(1<<(j-1))))ok=true;               // 左边有油库则覆盖
        if(j+1<m&&(cur&(1<<(j+1))))ok=true;                // 右边有油库则覆盖
        if(prev&(1<<j))ok=true;                            // 上一行同列有油库则覆盖
        if(nxt&(1<<j))ok=true;                             // 下一行同列有油库则覆盖
        if(!ok)return false;                               // 有一个格子没被覆盖就失败
    }
    return true;                                          // 全部格子都被覆盖则成功
}

int main(){                                               // 主函数
    ios::sync_with_stdio(false);                          // 加速输入输出
    cin.tie(nullptr);                                     // 加速输入输出

    cin>>n>>m;                                            // 读入 n,m
    for(int i=1;i<=n;i++){                                // 枚举行
        for(int j=1;j<=m;j++){                            // 枚举列
            cin>>F[i][j];                                 // 读入建库代价
        }
    }

    int FULL=(1<<m)-1;                                    // FULL 表示 m 列全选的掩码

    for(int i=0;i<=n;i++){                                // 初始化 dp
        for(int a=0;a<=FULL;a++){                         // 枚举 prev 掩码
            for(int b=0;b<=FULL;b++){                     // 枚举 cur 掩码
                dp[i][a][b]={INF,(int)1e9};               // 初始设为不可达
            }
        }
    }

    for(int cur=0;cur<=FULL;cur++){                       // 初始化第 1 行，上一行视作 0
        Node rc=rowCost(1,cur);                           // 计算第 1 行该方案的代价与数量
        dp[1][0][cur]=rc;                                 // 写入 dp[1][0][cur]
    }

    for(int i=1;i<=n-1;i++){                              // 从第 i 行转移到第 i+1 行
        for(int prev=0;prev<=FULL;prev++){                // 枚举 prev
            for(int cur=0;cur<=FULL;cur++){               // 枚举 cur
                Node base=dp[i][prev][cur];               // 取当前状态
                if(base.cost>=INF)continue;               // 不可达则跳过

                for(int nxt=0;nxt<=FULL;nxt++){           // 枚举下一行 nxt（第 i+1 行）
                    if(!rowCovered(i,prev,cur,nxt))continue; // 若第 i 行无法被覆盖则不合法

                    Node add=rowCost(i+1,nxt);            // 计算第 i+1 行采用 nxt 的代价与数量
                    Node cand={base.cost+add.cost,base.cnt+add.cnt}; // 合成候选答案

                    if(better(cand,dp[i+1][cur][nxt])){   // 若候选更优则更新
                        dp[i+1][cur][nxt]=cand;           // 更新 dp
                    }
                }
            }
        }
    }

    Node ans={INF,(int)1e9};                              // 最终答案初始化

    for(int prev=0;prev<=FULL;prev++){                    // 收尾：检查第 n 行被覆盖（nxt 视作 0）
        for(int cur=0;cur<=FULL;cur++){                   // 枚举第 n 行方案 cur
            Node base=dp[n][prev][cur];                   // 取 dp[n][prev][cur]
            if(base.cost>=INF)continue;                   // 不可达跳过
            if(!rowCovered(n,prev,cur,0))continue;        // 若第 n 行不被覆盖则不合法
            if(better(base,ans))ans=base;                 // 更新答案
        }
    }

    cout<<ans.cnt<<" "<<ans.cost<<endl;                   // 输出：油库数量 与 总代价
    return 0;                                             // 结束程序
}