题目链接:
题目大意:
给出一个n*n的矩阵,从左上角走到右下角,只能向右或向下走,问路径上的数之积末尾0最少的方案是什么。
题目分析:
- 首先我们要做两个预处理,处理出每个位置上的数包含多少个2的质因子和多少个5这个质因子
- 然后我们统计路径上弄到最少的2的方案数和最少的5的方案数。
- 这个转移方程很简单:定义dp[i][j]为走到点[i,j]时最少弄到给定质因数的个数,a[i][j]表示[i,j]位置上给定质因数的个数。
- dp[i][j]=min(dp[i−1][j],dp[i][j−1])+a[i][j]
- 然后我们需要证明ans=min(k,m),k代表弄到的最少的2的个数,m表示弄到的最少的5的个数。
- 首先因为我们一定可以选择一条路径,保证这条路径上其中一个质因数的个数不超过ans,所以ans是答案的上限。
- 然后因为我们如果能够找到两个质因数的最小值小于ans的情况时,存在一条路经能够导致kk
AC代码:
#include <iostream>
#include <cstring>
#include <cstdio>
#include <algorithm>
#define MAX 1007
using namespace std;
int n,x;
int dp[2][MAX][MAX];
int p[2][MAX][MAX];
void print ( int x , int y , int k , int f )
{
if ( x == 1 && y == 1 );
else if ( x == 1 ) print ( x , y-1 , k , 0);
else if ( y == 1 ) print ( x-1 , y , k , 1);
else
{
if ( dp[k][x][y] == dp[k][x-1][y] + p[k][x][y] )
print ( x-1 , y , k , 1 );
else print ( x , y-1 , k , 0);
}
if ( f == 3 ) return;
printf ( "%c" , f?'D':'R' );
}
int main ( )
{
while ( ~scanf ( "%d" , &n ) )
{
int flag = 0,a,b;
for ( int i = 1 ; i <= n ; i++ )
for ( int j = 1 ; j <= n ; j++ )
{
scanf ( "%d" , &x );
if ( !x )
{
flag = 1;
p[0][i][j]++;
p[1][i][j]++;
a = i , b = j;
continue;
}
while ( x%2 == 0 )
{
p[0][i][j]++;
x /= 2;
}
while ( x%5 == 0 )
{
p[1][i][j]++;
x /= 5;
}
}
memset ( dp , 0x3f , sizeof ( dp ) );
for ( int k = 0 ; k < 2 ; k++ )
for ( int i = 1 ; i <= n ; i++ )
for ( int j = 1 ; j <= n ; j++ )
{
if ( i-1 )
dp[k][i][j] = min ( dp[k][i][j] , dp[k][i-1][j] );
if ( j-1 )
dp[k][i][j] = min ( dp[k][i][j] , dp[k][i][j-1] );
if ( i == j && i == 1 )
dp[k][i][j] = 0;
dp[k][i][j] += p[k][i][j];
}
int ans = min ( dp[0][n][n] , dp[1][n][n] );
if ( ans > 1 && flag )
{
puts ( "1" );
for ( int i = 1 ; i < a ; i++ )
printf ( "%c" , 'D' );
for ( int j = 1 ; j < b ; j++ )
printf ( "%c" , 'R' );
for ( int i = a ; i < n ; i++ )
printf ( "%c" , 'D' );
for ( int j = b ; j < n ; j++ )
printf ( "%c" , 'R' );
puts ( "" );
continue;
}
printf ( "%d\n" , ans );
if ( dp[0][n][n] < dp[1][n][n] )
print ( n , n , 0 , 3 );
else print ( n , n , 1 , 3 );
puts ( "" );
}
}