题解 【[NOI Online 2021 入门组] 吃豆人】
TRZ_2007
2021-03-27 20:56:31
**[题解 【[NOI Online 2021 入门组] 吃豆人】](https://www.luogu.com.cn/problem/P7472)**
**update 2021.4.4**：Task 2 的做法，本题的 AC 代码
。
# Solution
Task1：暴力枚举每一个放置吃豆人的位置，然后暴力计算求最大值，时间复杂度 $\mathcal{O(n^5)}$，期望得分 30pts。
Task2：模拟每一个吃豆人所走的路线，枚举每一个点，计算最大值。相较 Task1 做法不同的是，我们这边可以先存下来赤豆人所走的路线，方向，在枚举完第二个吃豆人的起点与方向后再进行计算，而且正如正解所说，我们只需要枚举第一列就可以了。这样干掉了一个 $n$，时间复杂度为 $\mathcal{O(n^3)}$。
**正解**：观察吃豆人所走的路线，发现除了对角线之外其他的路径都可以重合（具体证明可以通过数学方法得到），而且关于每一个点，最多只会有两段路径和它重合，因此我们可以考虑计算每一段路径可以吃到的豆的数量，令 $f_i$ 表示从 $(1,i)$ 出发的路径能吃到多少的豆，$p_{i,j}$ 表示路径 $i$ 和 路径 $j$ 所重合的豆的数量，其中 $f$ 可以通过暴力模拟路径所计算，那么最终的答案就是 $\max {f_i+f_j-p_{i,j}}$，总的时间复杂度为 $\mathcal{O(n^2)}$，可以通过本题。
# Code
```cpp
#include <cstdio>
#include <cctype>
using namespace std;
const int N = 1009;
#define gc getchar
inline int read() {
int c = gc(), t = 1, n = 0;
while(isspace(c)) { c = gc(); }
if(c == '-') { t = -1, c = gc(); }
while(isdigit(c)) { n = n * 10 + c - '0', c = gc(); }
return n * t;
}
#undef gc
#define max(a,b) a > b ? a : b
int n,a[N][N],sum1[N][N],sum2[N][N],cnt[N],ans,tmp;
// 这里的 cnt 表示题解中的 f，两个sum分别表示斜上方和斜下方所走的路径的前缀和，方便我们的计算。
int x1,x2,x3,x4,y1,y2,y3,y4;
int main() {
n = read();
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= n;j++) a[i][j] = read();
}
for(int i = 1;i <= n;i++) {
for(int j = 1;j <= n;j++) {
sum1[i][j] = sum1[i - 1][j - 1] + a[i][j]; //斜下方
sum2[i][j] = sum2[i - 1][j + 1] + a[i][j]; //斜上方
}
}
cnt[1] = sum1[n][n]; cnt[n] = sum2[n][1]; //特殊情况：对角线
for(int i = 2;i < n;i++) {
cnt[i] = sum1[n][n - i + 1] + sum1[n - i + 1][n] + sum2[i][1] + sum2[n][n - i + 1];
cnt[i] = cnt[i] - a[1][i] - a[i][1] - a[n - i + 1][n] - a[n][n - i + 1];
//通过题解描述我们可以知道： Fi 所走的路径为：(1,i)->(n - i + 1,n) -> (n,n - i + 1) -> (i,1) -> (1,i)，所以把这四列加在一起，减去它们的交点就可以了
}
ans = -1;
for(int i = 1;i <= n;i++) {
for(int j = i + 1;j <= n;j++) {
tmp = cnt[i] + cnt[j];
if((j - i) % 2 == 0) { //如果两个起点的 i 的变化量是偶数的话，那么就会有交点，否则没有交点，可以用初中数学知识证明
x1 = 1 + (j - i) / 2; y1 = (i + j) / 2;
x2 = y1; y2 = x1;
x3 = n - y1 + 1; y3 = n - x1 + 1;
x4 = y3; y4 = x3;
if(x1 == x2 && x2 == x3 && x3 == x4) tmp -= a[x1][y1];
else if(x1 == x2 && x3 == x4 && x1 != x3) tmp -= (a[x1][y1] + a[x3][y3]);
else if(x1 == x3 && x2 == x4 && x1 != x4) tmp -= (a[x1][y1] + a[x2][y2]);
else tmp -= (a[x1][y1] + a[x2][y2] + a[x3][y3] + a[x4][y4]); //这几行 if 都属于去重，即减去 p(i,j)，可以提前算，在这里算也是可以的
}
ans = max(ans,tmp);
}
}
printf("%d\n",ans);
return 0;
}
```