先预处理每一行和每一列的敌人数总和，再在所有空位上取行和加列和的最大值。
OJ: luogu
题目 ID: P2356
难度:普及-
标签:模拟枚举
日期: 2026-06-18 23:54
题意
给定一个 n x n 的矩阵。
正数表示该位置敌人的数量，0 表示这个位置为空，可以站人。
如果站在一个空位 (i,j)，就能消灭第 i 行和第 j 列里的所有敌人。
要求输出能消灭敌人数的最大值。
思路
先看一个最直接的朴素解：
枚举每个空位，然后重新扫描它所在的整行和整列，统计这个位置能打到多少敌人。
cpp
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 105;
int n;
int a[MAXN][MAXN];
void solve() {
int ans = 0;
// 枚举每一个空位，真的把该行该列的敌人全部统计一遍。
for (int x = 1; x <= n; x++) {
for (int y = 1; y <= n; y++) {
if (a[x][y] != 0) {
continue;
}
int cur = 0;
for (int j = 1; j <= n; j++) {
cur += a[x][j];
}
for (int i = 1; i <= n; i++) {
cur += a[i][y];
}
ans = max(ans, cur);
}
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
}
}
solve();
return 0;
}这个做法的重复计算比较多。
其实一个空位 (i,j) 的答案只由两件事决定：
- 第
i行的总和 - 第
j列的总和
所以我们可以先预处理：
row_sum[i]：第i行总敌人数col_sum[j]：第j列总敌人数
这样每个空位的得分就能直接写成：
row_sum[i] + col_sum[j]
再在所有空位里取最大值即可。
因为空位本身是 0，这里不会有重复多算当前位置的问题。
代码
cpp
#include <bits/stdc++.h>
using namespace std;
const int MAXN = 1005;
int n;
int a[MAXN][MAXN];
int row_sum[MAXN];
int col_sum[MAXN];
void solve() {
int ans = 0;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
if (a[i][j] == 0) {
ans = max(ans, row_sum[i] + col_sum[j]);
}
}
}
cout << ans << '\n';
}
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
cin >> n;
for (int i = 1; i <= n; i++) {
for (int j = 1; j <= n; j++) {
cin >> a[i][j];
row_sum[i] += a[i][j];
col_sum[j] += a[i][j];
}
}
solve();
return 0;
}复杂度
时间复杂度是
总结
这题的关键在于把“每个空位的攻击结果”改写成“行和 + 列和”。
预处理完行列和之后，枚举空位就很直接了。