题解：B4140 [信息与未来 2016] 方格取数

· · 题解

分析

本题为没有任何难度的水题，先造出数据，然后直接按题意爆搜，遍历每一条值严格递增的路径，打擂台取最大值即可。 （同名题目，但难度天差地别）

Code

#include <bits/stdc++.h>
using namespace std;
int n, m, s;
int a[110][110];
int maxn = -1, maxx = -1;
void dfs(int x, int y, int ans) {
    maxn = max(maxn, ans); // 打擂台取最大值
    if(a[x+1][y] > a[x][y]) {
        dfs(x+1, y, ans + a[x+1][y]);
    }
    if(a[x][y+1] > a[x][y]) {
        dfs(x, y+1, ans + a[x][y+1]);
    }
    if(a[x-1][y] > a[x][y]) {
        dfs(x-1, y, ans + a[x-1][y]);
    }
    if(a[x][y-1] > a[x][y]) {
        dfs(x, y-1, ans + a[x][y-1]);
    }
}
int main() {
    scanf("%d%d%d", &n, &m, &s);
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            s = (s * 345) % 19997;
            a[i][j] = s % 10 + 1;
        }
    } // 生成数据
    for (int i = 1; i <= n; i++) {
        for (int j = 1; j <= m; j++) {
            dfs(i, j, a[i][j]); // 爆搜
            maxx = max(maxn, maxx);
            /* 这里需要注意！！！
             * 每一次爆搜取得的是从当前位置开始的最优解
             * 而不是全局最优解
             * 所以需要每爆搜一遍就更新答案
             */
            maxn = -1;
        }
    }
    printf("%d", maxx);
    return 0;
}

AC 记录