题目链接:http://codeforces.com/problemset/problem/2/B
题目大意:
给你一个nxn的矩形,找到一条从左上角到右下角的路径,使得该路径上所有数字的乘积的末尾0最少。
解题思路:
我们设k为2的因子数,m为5的因子数,那么一个数的末尾0的个数就是min(k,m)。
我们设dp[i][j][0]为从左上角到点(i,j)的乘积的最少2因子数,dp[i][j][1]为从左上角到点(i,j)的乘积的最少5因子数。
那么ans=min(dp[i][j][0],dp[i][j][1]),如果ans=dp[i][j][0]就按path[i][j][0]输出,若ans=dp[i][j][1]也同理。
注意存在0的情况,若果路径中有一个0那么末尾0为1,若ans>1,则构造一条经过0的路径输出。
代码:
#include<bits/stdc++.h>
#define lc(a) (a<<1)
#define rc(a) (a<<1|1)
#define MID(a,b) ((a+b)>>1)
#define fin(name) freopen(name,"r",stdin)
#define fout(name) freopen(name,"w",stdout)
#define clr(arr,val) memset(arr,val,sizeof(arr))
#define _for(i,start,end) for(int i=start;i<=end;i++)
#define FAST_IO ios::sync_with_stdio(false);cin.tie(0);
using namespace std;
typedef long long LL;
const int N=1e3+;
const int INF=0x3f3f3f3f;
const double eps=1e-; int n;
int mp[N][N],dp[N][N][],path[N][N][]; struct node{
int f,s;
node(int f,int s):f(f),s(s){}
}; bool judge(int x,int y){
if(x>&&x<=n&&y>&&y<=n) return true;
return false;
} void print(int x,int y,int type){
if(path[x][y][type]==-)
return;
if(path[x][y][type]==)
print(x-,y,type);
else
print(x,y-,type);
printf("%c",path[x][y][type]==?'D':'R');
} node cal(int x){
int f=,s=;
while(x){
if(x%==){
f++;
x/=;
}
else break;
}
while(x){
if(x%==){
s++;
x/=;
}
else break;
}
return node(f,s);
} int main(){
scanf("%d",&n);
int idx,idy;
bool flag=false;
memset(path,-,sizeof(path));
memset(dp,0x3f,sizeof(dp));
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
scanf("%d",&mp[i][j]);
if(mp[i][j]==){
idx=i;
idy=j;
flag=true;
}
}
}
dp[][][]=dp[][][]=;
for(int i=;i<=n;i++){
for(int j=;j<=n;j++){
node t=cal(mp[i][j]);
if(judge(i-,j)){
dp[i][j][]=dp[i-][j][];
dp[i][j][]=dp[i-][j][];
path[i][j][]=path[i][j][]=;
}
if(judge(i,j-)){
if(dp[i][j][]>dp[i][j-][]){
dp[i][j][]=dp[i][j-][];
path[i][j][]=;
}
if(dp[i][j][]>dp[i][j-][]){
dp[i][j][]=dp[i][j-][];
path[i][j][]=;
}
}
dp[i][j][]+=t.f;
dp[i][j][]+=t.s;
}
}
int ans=min(dp[n][n][],dp[n][n][]);
if(ans>&&flag){
puts("");
for(int i=;i<=idx;i++){
printf("D");
}
for(int j=;j<=n;j++){
printf("R");
}
for(int i=idx+;i<=n;i++){
printf("D");
}
return ;
}
printf("%d\n",ans);
if(ans==dp[n][n][])
print(n,n,);
else
print(n,n,);
return ;
}