本站于2023年9月4日。收到“大连君*****咨询有限公司”通知
说我们IIS7站长博客，有一篇博文用了他们的图片。
要求我们给他们一张图片6000元。要不然法院告我们
为避免不必要的麻烦，IIS7站长博客，全站内容图片下架、并积极应诉
博文内容全部不再显示，请需要相关资讯的站长朋友到必应搜索。谢谢！
另祝：版权碰瓷诈骗团伙，早日弃暗投明。
相关新闻：借版权之名、行诈骗之实，周某因犯诈骗罪被判处有期徒刑十一年六个月
叹！百花齐放的时代,渐行渐远!
https://www.luogu.com.cn/problem/CF2B
动态规划
\[f[i][j]表示从(1,1)走到(i,j)最少拥有的因子2数量\\
g[i][j]表示从(1,1)走到(i,j)最少拥有的因子5数量\\
转移显然\\
同时记录路径\\
取ans=min(f[n][n],g[n][n])，特判有0的情况\\
打印路径即可
\]
\(C++ Code:\)
#include<iostream>
#include<cstdio>
#include<algorithm>
#include<stack>
#define N 1005
#define INF 123456789
using namespace std;
int dic[2][2]={{-1,0},{0,-1}};
char h[2]={'D','R'};
stack<char>s;
int n,x,sx,sy,two[N][N],five[N][N],f[N][N],g[N][N],ff[N][N][2],gg[N][N][2];
char cf[N][N],cg[N][N];
bool zero;
int main()
{
scanf("%d",&n);
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
{
scanf("%d",&x);
if (!x)
{
sx=i;
sy=j;
zero=true;
} else
{
while (x&&(x%2==0))
{
two[i][j]++;
x/=2;
}
while (x&&(x%5==0))
{
five[i][j]++;
x/=5;
}
}
}
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
f[i][j]=g[i][j]=INF;
f[1][1]=two[1][1],g[1][1]=five[1][1];
for (int i=1;i<=n;i++)
for (int j=1;j<=n;j++)
if (i==1&&j==1)
continue; else
{
for (int k=0;k<2;k++)
{
int nh=i+dic[k][0],nl=j+dic[k][1];
if (nh<1||nh>n||nl<1||nl>n)
continue;
if (f[nh][nl]+two[i][j]<f[i][j])
{
f[i][j]=f[nh][nl]+two[i][j];
ff[i][j][0]=nh,ff[i][j][1]=nl;
cf[i][j]=h[k];
}
if (g[nh][nl]+five[i][j]<g[i][j])
{
g[i][j]=g[nh][nl]+five[i][j];
gg[i][j][0]=nh,gg[i][j][1]=nl;
cg[i][j]=h[k];
}
}
}
int ans=min(f[n][n],g[n][n]);
if (!zero||ans<=1)
{
printf("%d\n",ans);
int i=n,j=n;
while (i^1||j^1)
{
int Ri=i,Rj=j;
if (f[n][n]<=g[n][n])
s.push(cf[i][j]),i=ff[Ri][Rj][0],j=ff[Ri][Rj][1]; else
s.push(cg[i][j]),i=gg[Ri][Rj][0],j=gg[Ri][Rj][1];
}
while (!s.empty())
putchar(s.top()),s.pop();
putchar('\n');
} else
{
puts("1");
for (int i=1;i<sx;i++)
putchar('D');
for (int i=1;i<n;i++)
putchar('R');
for (int i=sx+1;i<=n;i++)
putchar('D');
putchar('\n');
}
return 0;
}
