传送门：https://ac.nowcoder.com/acm/contest/16081/I
题意
有一个n×m的网格地图，每个点有个值$a_{ij}$ ，现在牛牛要从(1，1)走到(n，m). 他可以往右边或者往下走，每次到一个点会获得当前的点权值，并将权值和mod 1e4+7. 当牛牛从不同方式走到(n，m)的时候能获得多少种权值和？
思路
这题给的mod很关键，只有1e4，然后n和m只有100，所以能猜出来复杂度为100*100*10000，1e8只能说很标准但又很危险。
设f[i][j][k]表示走到第i行第j列加上a[i][j]之后存在k这个权值，则转移可以从上面或者左边都可以。
$$f[i][j][k]=max(f[i-1][j][k-a[i][j]],f[i][j-1][k-a[i][j]])$$
注意mod的范围，不要RE，并且不要开ll，不要MLE，最好刚开始手动$a[i][j]\%mod$，不要WA。
复杂度为$O(n*m*mod)$。
Code（384MS）
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
| ##include "bits/stdc++.h"
using namespace std;
typedef long long ll;
int mod = 1e4 + 7;
const int N = 101;
const int M = 1e4 + 8;
int a[N][N];
bool dp[N][N][M];
inline int Mod(int x) {
if(x >= mod) return x % mod;
else if(x < 0) return x % mod + mod;
return x;
}
void solve() {
int n, m; scanf("%d%d",&n,&m);
for(int i = 1;i <= n; i++) {
for(int j = 1;j <= m; j++) {
scanf("%d",&a[i][j]);
a[i][j] %= mod;
}
}
dp[1][1][a[1][1]] = 1;
for(int i = 1;i <= n; i++) {
for(int j = 1;j <= m; j++) {
if(i == 1 && j == 1) continue;
for(int k = mod - 1;k >= 0; k--) {
int temp = Mod(k - a[i][j]);
dp[i][j][k] = max(dp[i][j - 1][temp], dp[i - 1][j][temp]);
}
}
}
int ans = 0;
for(int i = 0;i < mod; i++) ans += dp[n][m][i];
printf("%d\n",ans);
}
signed main() {
solve();
}
|
本文作者：jujimeizuo
本文地址： https://blog.jujimeizuo.cn/2021/05/06/nowcoder-beginner28-i/
本博客所有文章除特别声明外，均采用 CC BY-SA 3.0 协议。转载请注明出处！