题解：P11248 [GESP202409 七级] 矩阵移动

笑点解析：这个人所在城市考试当天刮台风了，没考，免费送了一次 12 月的考试。

设计这么一个东西：

$dp_{i,j}$ 表示到格子 $(i, j)$ 的最大分数。

本来还好，但现在的问题是，如果这个格子是‘？’，我哪儿知道到底可不可以变啊？万一变得太多了，那，那不就废了！万一少了，那我分不就没了？

所以我们需要到底还剩多少次机会呢？不好办，没法儿处理。

其实加一维记录就可以了。

于是我得到了这个状态：

$dp_{i, j, k}$ = 到格子 $(i, j)$ 且已经使用了 $k$ 次机会的最大值。

转移也很好推：

不是‘？’：

dp_{i, j, k} = \begin{cases} \max(dp_{i, j - 1, k}, dp_{i - 1, j, k}) + 1& (i, j) = 1\\ \max(dp_{i, j - 1, k}, dp_{i - 1, j, k})& (i, j) = 0\\ \end{cases}

就是从两种可能的上一步转移过来，注意横竖均可。

是‘？’：

dp_{i, j, k} = \begin{cases} \max(dp_{i, j - 1, k}, dp_{i - 1, j, k}) + 1& k = 0\\ \max(dp_{i, j - 1, k - 1}, dp_{i - 1, j, k - 1}) + 1& k > 0\\ \end{cases}

同上，注意 $k = 0$ 时不能使用机会。而且可以变的话当然是变了更好，所以 $k > 0$ 时可以无脑使用。

AC Code:

1
/*Code by Block_Fish*/
2
#include <bits/stdc++.h>
3

4
#define INF 0x3f3f3f3f
5
#define EPS 1e-8
6
#define FOR(i, l, r) for (ll(i) = (l); (i) <= (r); ++(i))
7
#define log printf
8
#define IOS                      \
9
  ios::sync_with_stdio(false); \
10
  cin.tie(nullptr);            \
11
  cout.tie(nullptr);
12

13
using namespace std;
14

15
typedef __int128 i128;
16
typedef long long ll;
17
typedef pair<ll, ll> PII;
18

19
const int N = 510, M = 310;
20
int m, n, t, x, a[N][N], dp[N][N][M], ans;  // dp[i][j][k] = (1, 1) 到(i, j)，已经使用了k次机会的最大值
21
string s;
22

23
template <typename T>
24

25
inline T read() {
26
  T sum = 0, fl = 1;
27
  char ch = getchar();
28
  for (; !isdigit(ch); ch = getchar())
29
    if (ch == '-') fl = -1;
30
  for (; isdigit(ch); ch = getchar()) sum = sum * 10 + ch - '0';
31
  return sum * fl;
32
}
33

34
template <typename T>
35

36
inline void write(T x) {
37
  if (x < 0) {
38
    putchar('-'), write<T>(-x);
39
    return;
40
  }
41
  static T sta[35];
42
  ll top = 0;
43
  do { sta[top++] = x % 10, x /= 10; } while (x);
44
  while (top) putchar(sta[--top] + 48);
45
}
46

47
int main() {
48
    IOS;
49
    cin >> t;
50
    while (t--) {
51
        cin >> n >> m >> x;
52
        FOR(i, 1, n) {
53
            cin >> s;
54
            for (int j = 0;j < m;++j) {
55
                if (s[j] == '?') a[i][j + 1] = -INF;
56
                else a[i][j + 1] = s[j] - '0';
57
            }
58
        }
59
        FOR(i, 1, n) FOR(j, 1, m) FOR(k, 0, x) {
60
              // 要用到 k - 1, 必须正序遍历。
61
            switch(a[i][j]) {
62
                case -INF:
63
                    if (k > 0) dp[i][j][k] = max(dp[i][j - 1][k - 1], dp[i - 1][j][k - 1]) + 1;
64
                    else dp[i][j][k] = max(dp[i][j - 1][k], dp[i - 1][j][k]);
65
                    break;
66
                case 1:
67
                    dp[i][j][k] = max(dp[i][j - 1][k], dp[i - 1][j][k]) + 1;
68
                    break;
69
                case 0:
70
                    dp[i][j][k] = max(dp[i][j - 1][k], dp[i - 1][j][k]);
71
                    break;
72
            }
73
        }
74
        FOR(i, 0, x) ans = max(ans, dp[n][m][i]);  // 不超过就是不一定，要遍历一遍
75
        cout << ans << endl;
76
        memset(dp, 0, sizeof(dp));
77
        memset(a, 0, sizeof(a));
78
        ans = -INF;
79
        // 多组数据要清空
80
    }
81
  return 0;
82
}

AC 记录~

理解万岁！

音乐

音乐

支持与分享

评论区