The least round way
给你一个n*n的矩阵,求从左上角到右下角的所有路径中,最后乘机末尾0最小的路径,输出末尾0的个数和路径
题解
将每个数提取质因数2和5,然后dp每个点2和5的个数,最后取两个中最小的,如果矩阵中有0, 且5和2的最小值不为0,则随便输出一个经过0的路径
#include <iostream>
#include <cstdio>
using namespace std;
const int N=1005;
int l[N][N][3],dp[N][N][3];
char pre[N][N][2];
int get2(int x)
{
int res = 0;
while(x % 2 == 0)
{
res++;
x /= 2;
}
return res;
}
int get5(int x)
{
int res = 0;
while(x % 5 == 0)
{
res ++;
x /= 5;
}
return res;
}
void print(int x,int y,int q)
{
if(x==1 && y==1) return ;
if(pre[x][y][q] == 'R'){
print(x,y-1,q);
printf("R");
}
else{
print(x-1,y,q);
printf("D");
}
}
int main()
{
int n,a,x=-1,y=-1;
cin >> n;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
cin >> a;
if(a == 0){
l[i][j][0] = 0;
l[i][j][1] = 0;
x = i;
y = j;
}
else{
l[i][j][0] = get2(a);
l[i][j][1] = get5(a);
}
}
}
for(int i = 1;i <=n ;i++){
dp[1][i][0] = dp[1][i-1][0] + l[1][i][0];
dp[1][i][1] = dp[1][i-1][1] + l[1][i][1];
pre[1][i][0] = 'R';
pre[1][i][1] = 'R';
dp[i][1][0] = dp[i-1][1][0] + l[i][1][0];
dp[i][1][1] = dp[i-1][1][1] + l[i][1][1];
pre[i][1][0] = 'D';
pre[i][1][1] = 'D';
}
for(int i = 2 ; i <= n ;i++){
for(int j = 2; j <= n; j++){
if(dp[i-1][j][0] < dp[i][j-1][0]){
dp[i][j][0] = dp[i-1][j][0] + l[i][j][0];
pre[i][j][0] = 'D';
}
else{
dp[i][j][0] = dp[i][j-1][0] + l[i][j][0];
pre[i][j][0] = 'R';
}
if(dp[i-1][j][1] < dp[i][j-1][1]){
dp[i][j][1] = dp[i-1][j][1] + l[i][j][1];
pre[i][j][1] = 'D';
}
else{
dp[i][j][1] = dp[i][j-1][1] + l[i][j][1];
pre[i][j][1] = 'R';
}
}
}
if(x==-1){
if(dp[n][n][0] < dp[n][n][1]){
cout << dp[n][n][0] << endl;
print(n,n,0);
}
else{
cout << dp[n][n][1] << endl;
print(n,n,1);
}
}
else if(x!=-1 && min(dp[n][n][0],dp[n][n][1]) == 0){
cout << "0" << endl;
if(dp[n][n][0] == 0) print(n,n,0);
else print(n,n,1);
}
else{
cout << "1" << endl;
for(int i=1;i<=n;i++){
if(i==x){
for(int j=1;j<n;j++){
printf("R");
}
}
else{
printf("D");
}
}
}
return 0;
}