Following Directions

题意

有一个 $(N+1)\times (N+1)$ 的网格。左上角 $N\times N$ 的每个格子里有一头牛和一个箭头，箭头只会指向右边 R 或下边 D。

最右一列和最下一行是饲料槽，每个饲料槽有一个喂一头牛的费用。

每天所有牛从自己的初始格子出发，沿着箭头走到某个饲料槽。现在有 $Q$ 次操作，每次把某个内部格子的箭头翻转，并要求输出翻转前以及每次翻转后的总费用。

思路

先看一个小数据暴力。每次翻转后，让每头牛重新沿箭头走到边界饲料槽，再重新计算总费用。

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 19:12
 * update_at: 2026-07-11 19:14
 */
// brute.cpp：小数据暴力解，用来帮助理解题意并辅助对拍。
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 35;

int n, q;
char dirc[MAXN][MAXN];
int cost[MAXN][MAXN];

ll calc_answer() {
    ll ans = 0;
    for (int sx = 1; sx <= n; sx++) {
        for (int sy = 1; sy <= n; sy++) {
            int x = sx;
            int y = sy;
            while (x <= n && y <= n) {
                if (dirc[x][y] == 'R') {
                    y++;
                } else {
                    x++;
                }
            }
            ans += cost[x][y];
        }
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s >> cost[i][n + 1];
        for (int j = 1; j <= n; j++) {
            dirc[i][j] = s[j - 1];
        }
    }
    for (int j = 1; j <= n; j++) {
        cin >> cost[n + 1][j];
    }

    cout << calc_answer() << '\n';

    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        if (dirc[x][y] == 'R') {
            dirc[x][y] = 'D';
        } else {
            dirc[x][y] = 'R';
        }
        cout << calc_answer() << '\n';
    }

    return 0;
}

暴力每次要从所有 $N^2$ 个起点重新走路径，太慢。

官方做法维护一个数组 cnt[i][j]：

text

1cnt[i][j] = 有多少头牛会经过格子 (i,j)

初始时，每个内部格子都有一头自己的牛，所以先让 cnt[i][j] += 1。由于箭头只会向右或向下，按从上到下、从左到右的顺序处理格子时，一个格子的 cnt 已经确定，可以直接把它累加给箭头指向的下一个格子。

用样例初始方向看，内部格子和边界饲料槽大致如下：

位置	内容	初始经过牛数
`(1,1)`	`R`	1
`(1,2)`	`R`	2
`(1,3)`	费用 `1`	2
`(2,1)`	`D`	1
`(2,2)`	`D`	1
`(3,1)`	费用 `100`	1
`(3,2)`	费用 `500`	1

可以看到，边界饲料槽的 cnt 就是有多少头牛最后吃这个槽。总费用就是：

text

1sum(cnt[饲料槽] * cost[饲料槽])

现在考虑翻转 (x,y) 的箭头。有 cnt[x][y] 头牛会经过这个格子，它们后面的路径都会改变；其它没有经过 (x,y) 的牛完全不受影响。

所以更新分两步：

沿旧箭头路径往后走，把这些格子的 cnt 都减去 cnt[x][y]；
翻转箭头；
沿新箭头路径往后走，把这些格子的 cnt 都加上 cnt[x][y]。

当路径走到边界饲料槽时，同步把答案减去或加上 cnt[x][y] * cost。

一条路径最多向右走 $N$ 步、向下走 $N$ 步，因此单次翻转只需要 $O(N)$ 。

代码

cpp

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100/**
 * Author by Rainboy blog: https://rainboylv.com github: https://github.com/rainboylvx
 * rbook: -> https://rbook.roj.ac.cn  https://rbook2.roj.ac.cn
 * rainboy的学习导航网站: https://idx.roj.ac.cn
 * create_at: 2026-07-11 19:12
 * update_at: 2026-07-11 19:14
 */
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

const int MAXN = 1505;

int n, q;
char dirc[MAXN][MAXN]; // 内部格子的箭头方向
int cost[MAXN][MAXN];  // 边界饲料槽费用
ll cnt[MAXN][MAXN];    // cnt[i][j] 表示有多少头牛经过这个格子
ll answer;

void add_path(int x, int y, ll delta) {
    int i = x;
    int j = y;

    // 从 (x,y) 指向的下一个格子开始更新，(x,y) 本身经过数量不变。
    while (i <= n && j <= n) {
        if (dirc[i][j] == 'R') {
            j++;
        } else {
            i++;
        }

        cnt[i][j] += delta;
        if (i == n + 1 || j == n + 1) {
            answer += delta * cost[i][j];
        }
    }
}

void build_initial() {
    answer = 0;
    for (int i = 1; i <= n + 1; i++) {
        for (int j = 1; j <= n + 1; j++) {
            if (i <= n && j <= n) {
                cnt[i][j]++;
                if (dirc[i][j] == 'R') {
                    cnt[i][j + 1] += cnt[i][j];
                } else {
                    cnt[i + 1][j] += cnt[i][j];
                }
            } else if (i != n + 1 || j != n + 1) {
                answer += cnt[i][j] * cost[i][j];
            }
        }
    }
}

void flip_cell(int x, int y) {
    ll cows = cnt[x][y];

    add_path(x, y, -cows);

    if (dirc[x][y] == 'R') {
        dirc[x][y] = 'D';
    } else {
        dirc[x][y] = 'R';
    }

    add_path(x, y, cows);
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);

    cin >> n;
    for (int i = 1; i <= n; i++) {
        string s;
        cin >> s >> cost[i][n + 1];
        for (int j = 1; j <= n; j++) {
            dirc[i][j] = s[j - 1];
        }
    }
    for (int j = 1; j <= n; j++) {
        cin >> cost[n + 1][j];
    }

    build_initial();

    cout << answer << '\n';
    cin >> q;
    while (q--) {
        int x, y;
        cin >> x >> y;
        flip_cell(x, y);
        cout << answer << '\n';
    }

    return 0;
}

复杂度

初始 cnt 按网格顺序计算，时间复杂度 $O(N^2)$ 。

每次翻转只更新旧路径和新路径，时间复杂度 $O(N)$ 。

总时间复杂度为 $O(N^2+NQ)$ ，空间复杂度为 $O(N^2)$ 。

总结

本题的关键不是重新模拟所有牛，而是维护“有多少牛经过每个格子”。

翻转一个箭头只会影响经过这个格子的那一批牛，并且它们只在后续路径上发生变化；沿旧路径减、沿新路径加，就能增量维护答案。

目录

题意

思路

代码

复杂度

总结