题目链接: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......时,又该怎么做呢?
代码:
#include<iostream>
#include<stdio.h>
#include<algorithm>
#include<queue>
#include<math.h>
#include<string.h>
#include<stdlib.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
#define re(i,n) ;i<n;i++)
int n;
;
int a[maxn][maxn];
int two[maxn][maxn], five[maxn][maxn];
int s[maxn][maxn][];
void go(int c[maxn][maxn], int x){
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
if (a[i][j] == 0){
c[i][j] = 1e6; continue;
}
int cnt = ;
; k /= x)cnt++;
c[i][j] = cnt;
}
}
}
void work(int c[maxn][maxn], int cc[maxn][maxn]){
re(i, n + 1)s[0][i][0] = s[0][i][1] = s[i][0][0] = s[i][0][1] = 1e6;
s[0][1][0] = s[0][1][1] = s[1][0][0] = s[1][0][1] = 0;
for (int i = 1; i <= n; i++){
for (int j = 1; j <= n; j++){
if (s[i - 1][j][0] == s[i][j - 1][0]){
s[i][j][0] = c[i][j] + s[i][j - 1][0];
s[i][j][1] = cc[i][j]+min(s[i][j - 1][1], s[i - 1][j][1]);
}
][j][]< s[i][j - ][]){
s[i][j][0] = s[i - 1][j][0] + c[i][j];
s[i][j][1] = s[i - 1][j][1] + cc[i][j];
}
else{
s[i][j][0] = s[i][j-1][0] + c[i][j];
s[i][j][1] = s[i][j-1][1] + cc[i][j];
}
}
}
}
int main(){
freopen("in.txt", "r", stdin);
cin >> n;
re(i, n)re(j, n)scanf("%d", &a[i + 1][j + 1]);
go(two, 2), go(five, 5);
work(two, five); int p = min(s[n][n][0], s[n][n][1]);
work(five, two); int q = min(s[n][n][0], s[n][n][1]);
cout << min(p, q) << endl;
return 0;
}