hihocoder1241 Best Route in a Grid
题目链接:hihocoder 1241
题意:
n*n的格阵,每个方格内有一个数字.蚂蚁从左上角走到右下角,数字是零的方格不能走,只能向右向下走.蚂蚁走的路径上全部方格的的乘积为s,要使s低位0的个数尽量少.问,最少s的末尾包含几个0.
分析:
10=2*5,所以只要统计蚂蚁路径上2的个数和5的个数,二者之中的较小者即为s末尾0的个数.
假设2的个数为x,5的个数为y.
对于路径(x,y),答案是min(x,y).
"路径(p,q)比路径(x,y)好"的充要条件"min(p,q)<min(x,y)".
最优路径(x,y)中x为最小值或者y为最小值.
这个问题可以进行延伸:将路径上数字的乘积用k进制来表示,使得末尾0的个数尽量少.对k进行因子分解,当k是若干个质数的乘积时,k=p1*p2*p3*p4...,对于每一个pi进行一次动归.当上边的主键等于左边时,就应该比较剩余的值,有点不好整了,还是两个质数之积比较简单.当k=p1^m1*p2^m2......时,又该怎么做呢?
代码:
1 #include<iostream> 2 #include<stdio.h> 3 #include<algorithm> 4 #include<queue> 5 #include<math.h> 6 #include<string.h> 7 #include<stdlib.h> 8 using namespace std; 9 typedef long long ll; 10 typedef unsigned long long ull; 11 #define re(i,n) for(int i=0;i<n;i++) 12 int n; 13 const int maxn = 1007; 14 int a[maxn][maxn]; 15 int two[maxn][maxn], five[maxn][maxn]; 16 int s[maxn][maxn][2]; 17 void go(int c[maxn][maxn], int x){ 18 for (int i = 1; i <= n; i++){ 19 for (int j = 1; j <= n; j++){ 20 if (a[i][j] == 0){ 21 c[i][j] = 1e6; continue; 22 } 23 int cnt = 0; 24 for (int k = a[i][j]; k%x == 0; k /= x)cnt++; 25 c[i][j] = cnt; 26 } 27 } 28 } 29 void work(int c[maxn][maxn], int cc[maxn][maxn]){ 30 re(i, n + 1)s[0][i][0] = s[0][i][1] = s[i][0][0] = s[i][0][1] = 1e6; 31 s[0][1][0] = s[0][1][1] = s[1][0][0] = s[1][0][1] = 0; 32 for (int i = 1; i <= n; i++){ 33 for (int j = 1; j <= n; j++){ 34 if (s[i - 1][j][0] == s[i][j - 1][0]){ 35 s[i][j][0] = c[i][j] + s[i][j - 1][0]; 36 s[i][j][1] = cc[i][j]+min(s[i][j - 1][1], s[i - 1][j][1]); 37 } 38 else if (s[i - 1][j][0]< s[i][j - 1][0]){ 39 s[i][j][0] = s[i - 1][j][0] + c[i][j]; 40 s[i][j][1] = s[i - 1][j][1] + cc[i][j]; 41 } 42 else{ 43 s[i][j][0] = s[i][j-1][0] + c[i][j]; 44 s[i][j][1] = s[i][j-1][1] + cc[i][j]; 45 } 46 } 47 } 48 } 49 int main(){ 50 freopen("in.txt", "r", stdin); 51 cin >> n; 52 re(i, n)re(j, n)scanf("%d", &a[i + 1][j + 1]); 53 go(two, 2), go(five, 5); 54 work(two, five); int p = min(s[n][n][0], s[n][n][1]); 55 work(five, two); int q = min(s[n][n][0], s[n][n][1]); 56 cout << min(p, q) << endl; 57 return 0; 58 }