题目大意：
给定一个数组a，长度为n，要求从其中选择若干个数使得这些数的乘积的最后一位数等于m的数最大。
题目意思很简单，但由于数据范围较大我们需要对每个数取log将其转化我对数的加法运算。
这样我们可以很容易的看出这道题于01背包之间的联系，从n个数中选择若干个数使其的和最大且乘法的最后一位数为m。
但是由于我们将其转化为了对数运算，所以我们需要聪明的额外考虑到一些事：我们将其转化为加法之后当我们选择第一个数时由于之间的数是0没办法取log，因此我们需要进行特判即
①当这个数为第一个数时我们需要直接将其变为当前的数，不能从上一个状态转移过来。
②当这个数不为第一个数时我们可以直接从上一层转移过来，不过我们需要判断上一层的状态是否为0，因为如果为0那么说明我们这个数是第一个数。
代码：
1 #include <iostream>
2 #include <algorithm>
3 #include <cstdio>
4 #include <cstring>
5 #include <cmath>
6 #include <vector>
7
8 using namespace std;
9
10 const int N = 100010;
11
12 int g[N];
13 double lg[N];
14 struct Node
15 {
16 bool flag;
17 int x, y; // 记录是从哪个转移过来
18 }pre[N][10];
19 double f[N][10];
20 int n, m;
21
22 int main()
23 {
24 cin >> n >> m;
25 for (int i = 1; i <= n; i ++ )
26 {
27 cin >> g[i];
28 lg[i] = log((double)g[i]);
29 }
30
31 for (int i = 1; i <= n; i ++ )
32 {
33 int mod = g[i] % 10;
34 f[i][mod] = lg[i];
35 pre[i][mod] = {true, 0, 0};
36
37 for (int j = 0; j < 10; j ++ )
38 {
39 if (f[i][j] < f[i - 1][j])
40 {
41 f[i][j] = f[i - 1][j];
42 pre[i][j] = {false, i - 1, j}; // 不选当前数
43 }
44
45 for (int k = 0; k < 10; k ++ ) // 选当前数
46 if (k * mod % 10 == j && (f[i][j] < f[i - 1][k] + lg[i]) && f[i - 1][k])
47 {
48 f[i][j] = f[i - 1][k] + lg[i];
49 pre[i][j] = {true, i - 1, k};
50 }
51 }
52 }
53
54 for (int i = 1; i <= n; i ++ )
55 {
56 for (int j = 0; j < 10; j ++ )
57 cout << f[i][j] << '\t';
58 cout << endl;
59 }
60
61 if (f[n][m] == 0) cout << -1 << endl;
62 else
63 {
64 vector<int> res;
65 int x = n, y = m;
66 while (x)
67 {
68 int prex = x, prey = y;
69 if (pre[x][y].flag) res.push_back(g[x]);
70 x = pre[prex][prey].x, y = pre[prex][prey].y;
71 }
72
73 cout << res.size() << endl;
74 for (int i = 0; i < res.size(); i ++ )
75 cout << res[i] << ' ';
76 cout << endl;
77 }
78
79 return 0;
80 }