Nule 题解
1.题意简述：
给定一个N行N列的非负整数方阵，从左上角(1,1)出发，只能向下或向右走，且不能到达值为0的方格，求出一条到达右下角的最佳路径，所谓最佳路径是指途径的数的乘积的末尾连续的0最少。
2.样例解释：
4
1 3 0 0
0 8 2 25
6 5 0 3
0 15 7 4
2
这个样例有多重走法，这里给出两个：
1. 1->3->8->2->25->3->4 最终结果为14400
2.1->3->8->5->15->7->4 最终结果为50400
3.思路：
还记不记得以前做过的一道题：给出 n，求 n! 末尾含0的个数。
当时我们的思路是对于 \(1\) 到 \(n\) 的每个数找出其含质因子 \(2\) 和 \(5\) 的个数， \(0\) 的个数就是其最小值。
那么本题我们可以采用同样的思路：开出两个二维数组 \(dp2[i][j]\) 和 \(dp5[i][j]\)，用于存储当走到第 \(i\) 行第 \(j\) 列时路径上含 \(2\) 的个数和含 \(5\) 的个数。
再分别做一遍动态规划，求出终点最小含 \(2\) 的个数和最小含 \(5\) 的个数，最终最少含 \(0\) 的个数就是其最小值。
3.注意
注意题目中说不能经过权值为 \(0\) 的边，所以我们在算每个点的权值含 \(2\) 的 \(5\) 的个数时要特判一下，如果权值为 \(0\)，那么将其含 \(2\) 和含 \(5\) 的个数为无穷大，这样在状态更新时，系统就不会选择含 \(2\) 和 \(5\) 较多的数。
然后再贴一下状态转移方程：
dp[i][j] = min (dp[i][j], min (dp[i - 1][j], dp[i][j - 1])) + prime (a[i][j]);
这里的 \(prime\) 函数指分别判断每个数含 \(2\) 和 \(5\) 的个数。
4.代码
#include <iostream>
#include <algorithm>
#include <cstring>
//define int long long
using namespace std;
#define N 1010
#define For(i,j,k) for(int i=j;i<=k;i++)
#define IOS ios::sync_with_stdio(),cin.tie(),cout.tie()
int n, a[N][N], dp[N][N];
//我这里只用了一个二维数组，分两次判断每个数含2和含5的个数。
int prime_2 (int x) {
if (x == 0) return 0x3f3f3f3f;
//特判权值为0的情况
int ans = 0;
while (x % 2 == 0) {
x /= 2;
ans ++;
} //只要这个数还能被2整除，就将答案加1
return ans;
}
int prime_5 (int x) {
if (x == 0) return 0x3f3f3f3f;
//特判权值为0的情况
int ans = 0;
while (x % 5 == 0) {
x /= 5;
ans ++;
}//只要这个数还能被5整除，就将答案加1
return ans;
}
int main () {
IOS;
cin >> n;
For (i, 1, n) {
For (j, 1, n) {
cin >> a[i][j];
}
}
//现将dp数组初始化为一个很大的数
memset (dp, 0x3f, sizeof dp);
dp[1][1] = 0; //将起点的值更新为0
For (i, 1, n) {
For (j, 1, n) {
dp[i][j] = min (dp[i][j], min (dp[i - 1][j], dp[i][j - 1])) + prime_2 (a[i][j]);
//套用状态转移方程
}
}
int ans = dp[n][n]; //将终点最小含2的个数存储在ans中
memset (dp, 0x3f, sizeof dp);
dp[1][1] = 0; //第二次dp，要重新赋初值
For (i, 1, n) {
For (j, 1, n) {
dp[i][j] = min (dp[i][j], min (dp[i - 1][j], dp[i][j - 1])) + prime_5 (a[i][j]);
}
}
//输出终点最小含2的个数与最小含5的个数的最小值
cout << min(dp[n][n], ans) << endl;
return 0;
}