第五课：动规

🔗 引用站外地址，请注意甄别
第五课：动规
517coding

A：最少末尾零

🔗 引用站外地址，请注意甄别
最少末尾零
517coding

记录 $2$ 最少的路径的 $2$ 的个数和 $5$ 最少的路径的 $5$ 的个数，最后取较小值即可

注意特判数组中有 $0$ 的情况

$dp_{ij0}$ 表示走到 $i$ 行 $j$ 列 $2$ 的最少个数

$dp_{ij1}$ 表示走到 $i$ 行 $j$ 列 $5$ 的最少个数

状态转的时候可以先转移第一行和第一列，这样减少思考

然后其余的状态由上面和左面转移即可

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
#include<bits/stdc++.h>
using namespace std;

const int N = 1010;

int dp[N][N][2];
int lst[N][N][2];

int flag = -1,n,x;
int mp[N][N][2];

char s[N*5];
int tot;
int main() {
    scanf("%d",&n);
    for(int i = 1; i <= n; i++) {
        for(int j = 1; j <= n; j++) {
            scanf("%d", &x);
            if(x != 0) {
                while(x % 2 == 0) x /= 2,mp[i][j][0]++;
                while(x % 5 == 0) x /= 5,mp[i][j][1]++;
            }
            else flag = i,mp[i][j][0] = mp[i][j][1] = 1000;
        }
    }
    for(int op = 0; op < 2; op++) {
        dp[1][1][op] = mp[1][1][op];
        for(int i = 2; i <= n; i++) {
            lst[1][i][op] = 1;lst[i][1][op] = -1;
            dp[1][i][op] = dp[1][i-1][op] + mp[1][i][op];
            dp[i][1][op] = dp[i-1][1][op] + mp[i][1][op];
        }
        for(int i = 2; i <= n; i++) {
            for(int j = 2; j <= n; j++) {
                if(dp[i][j-1][op] < dp[i-1][j][op]) lst[i][j][op] = 1, dp[i][j][op] = dp[i][j - 1][op] + mp[i][j][op];
                else lst[i][j][op] = -1, dp[i][j][op] = dp[i - 1][j][op] + mp[i][j][op];
            }
        }
    }
    if(flag != -1 && min(dp[n][n][0],dp[n][n][1])) {
        printf("1\n");
        for(int i = 2; i <= flag; i++) printf("D");
        for(int j = 2; j <= n; j++) printf("R");
        for(int i = flag + 1; i <= n; i++) printf("D");
        return 0;
    }
    int ans;
    if(dp[n][n][0] < dp[n][n][1]) ans = 0;
    else ans = 1;
    printf("%d\n",min(dp[n][n][0],dp[n][n][1]));
    int nowx = n, nowy = n;
    while(true) {
        if(lst[nowx][nowy][ans] == 1) nowy--, s[++tot] = 'R';
        else nowx--, s[++tot] = 'D';
        if(nowx == 1 && nowy == 1) break;
    }
    for(int i = tot;i >= 1;i--) putchar(s[i]);
    return 0;
}

B：凑硬币

🔗 引用站外地址，请注意甄别
凑硬币
517coding

中级班原题，多重背包问题

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
#include <bits/stdc++.h>
using namespace std;

const int N = 100010;

int f[N], v[N];
int a[N], s[N];
int main() {
	int n, m;
	scanf("%d%d", &n, &m);
	int sum = 0, tot = 0;
	for (int i = 1; i <= n; i++) {
		scanf("%d", &a[i]);
	}
	for (int i = 1; i <= n; i++) {
		scanf("%d", &s[i]);
		int t = 1;
		while(s[i] >= t) {
			v[++tot] = a[i] * t;
			s[i] -= t;
			t *= 2;
		}
		v[++tot] = a[i] * s[i];
	}
	f[0] = 1;
	for (int i = 1; i <= tot; i++) {
		for (int j = m; j >= 1; j--) {
			if (f[j - v[i]] == 1) f[j] = 1;
		}
	}
	for (int i = 1; i <= m; i++) {
		if (f[i] == 1) sum++;
	}
	printf("%d\n", sum);
	return 0;
}