青岛市赛2021 初中组 T2 跳格子 题解

· · 题解

跳格子

5分 a_{i, j} \leq 0

显然可以全取一遍

#include <stdio.h>

long long ans;
int n, m, a;

int main() {
    scanf("%d%d", &n, &m); n *= m;
    for (; n; --n) scanf("%d", &a), ans += a;
    printf("%lld", ans);
    return 0;
}

另外10分 n, m \leq 5

Depth First Search

#include <stdio.h>

int n, m, a[1005][1005];
long long ans = 0x3fffffffffffffff;

void dfs(int k, int rmost, long long sum) {
    if (!k) {
        if (sum < ans) ans = sum;
        return;
    }
    long long nsum = 0;
    for (int i = rmost; i; --i) {
        nsum += a[k][i];
        for (int j = i; j <= rmost; ++j)
            dfs(k - 1, j, sum + nsum);
    }
}

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%d", a[i] + j);
    for (int i = 1; i <= m; ++i)
        dfs(n, i, 0);
    printf("%lld", ans);
    return 0;
}

好像得了20分

另外15分 n = 2

枚举向上走的点，记录前缀和、后缀和、前缀和的前缀最大、后缀和的后缀最大，这样能O(1)计算当前行最优的走法。

#include <stdio.h>

int n, m, a[1005][1005], sump[1005][1005], maxp[1005][1005], sums[1005][1005], maxs[1005][1005], ans;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j)
            scanf("%d", a[i] + j);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            sump[i][j] = sump[i][j - 1] + a[i][j];
            maxp[i][j] = maxp[i][j - 1];
            if (sump[i][j] > maxp[i][j]) maxp[i][j] = sump[i][j];
        }
    for (int i = 1; i <= n; ++i)
        for (int j = m; j; --j) {
            sums[i][j] = sums[i][j + 1] + a[i][j];
            maxs[i][j] = maxs[i][j + 1];
            if (sums[i][j] > maxs[i][j]) maxs[i][j] = sums[i][j];
        }
    for (int i = 1; i <= m; ++i)
        if (sums[2][i] - maxs[2][i + 1] - maxp[1][i - 1] + sump[1][i] < ans)
            ans = sums[2][i] - maxs[2][i + 1] - maxp[1][i - 1] + sump[1][i];
    printf("%d", ans);
    return 0;
}

25分是什么鬼

另外20分 n, m \leq 90

不会，留给乱搞

另外20分 n, m \leq 400

设dp_{i, j}表示要从(i, j)向上走时的最小分数，则dp_{i, j} = \underset{j \leq k \leq m} \min \left\{ dp_{i + 1, k} + sum_{i, k} - maxx_{i, j - 1} \right\}

时间复杂度O(nm^2)

#include <stdio.h>

int n, m, a[1005][1005], sum[1005][1005], maxx[1005][1005];
long long dp[1005][1005], ans = 0x3fffffffffffffff;

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            scanf("%d", a[i] + j);
            sum[i][j] = sum[i][j - 1] + a[i][j];
            maxx[i][j] = maxx[i][j - 1];
            if (sum[i][j] > maxx[i][j]) maxx[i][j] = sum[i][j];
        }
    for (int i = n; i; --i)
        for (int j = 1; j <= m; ++j) {
            dp[i][j] = 0x3fffffffffffffff;
            for (int k = j; k <= m; ++k)
                if (dp[i + 1][k] + sum[i][k] - maxx[i][j - 1] < dp[i][j])
                    dp[i][j] = dp[i + 1][k] + sum[i][k] - maxx[i][j - 1];
        }
    for (int j = m; j; --j)
        if (dp[1][j] < ans) ans = dp[1][j];
    printf("%lld", ans);
    return 0;
}

好像开O2可以艹过去

常数小的O(nm^2)一秒完全不虚

100分 n, m \leq 10^3

考虑优化转移。这个dp_{i, j} = \underset{j \leq k \leq m} \min \left\{ dp_{i + 1, k} + sum_{i, k} { \color{RED} - maxx_{i, j - 1} } \right\}中的- maxx_{i, j - 1}显然和k无关，所以我们可以把它提出来。然后这就是个单点修改区间查最小值的问题，线段树解决

一定又是数据结构学傻了。

可以直接维护后缀最小来解决，当然也可以直接用dp_{i, j + 1}转移。

dp_{i, j} = \underset{j \leq k \leq m} \min \left\{ dp_{i + 1, k} + sum_{i, k} \right\} - maxx_{i, j - 1} \\ = \min \left\{ dp_{i + 1, j} + sum_{i, j}, \underset{j + 1 \leq k \leq m} \min \left\{ dp_{i + 1, k} + sum_{i, k} \right\} \right\} - maxx_{i, j - 1} \\ = \min \left\{ dp_{i + 1, j} + sum_{i, j}, \underset{j + 1 \leq k \leq m} \min \left\{ dp_{i + 1, k} + sum_{i, k} \right\} - maxx_{i, j} + maxx_{i, j} \right\} - maxx_{i, j - 1} \\ = \min \left\{ dp_{i + 1, j} + sum_{i, j}, dp_{i, j + 1} + maxx_{i, j} \right\} - maxx_{i, j - 1} 
#include <stdio.h>
#include <string.h>

int n, m, a[1005][1005], maxx[1005][1005], sum[1005][1005];
long long dp[1005][1005], ans = 0x3fffffffffffffff;

inline long long min(long long a, long long b) { return a < b ? a : b; }

int main() {
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i)
        for (int j = 1; j <= m; ++j) {
            scanf("%d", a[i] + j);
            sum[i][j] = a[i][j] + sum[i][j - 1];
            maxx[i][j] = maxx[i][j - 1] > sum[i][j] ? maxx[i][j - 1] : sum[i][j];
        }
    memset(dp, 0x3f, sizeof dp);
    for (int j = m; j; --j) dp[n][j] = min(sum[n][j], dp[n][j + 1] + maxx[n][j]) - maxx[n][j - 1];
    for (int i = n - 1; i; --i)
        for (int j = m; j; --j)
            dp[i][j] = min(dp[i + 1][j] + sum[i][j], dp[i][j + 1] + maxx[i][j]) - maxx[i][j - 1];
    for (int j = m; j; --j) ans = min(ans, dp[1][j]);
    printf("%lld", ans);
    return 0;
}