题解 【[NOI Online 2021 入门组] 吃豆人】

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

#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;
}