CF2B The least round way 题解
都是泪呀。。。↑
题目传送门
题意（直接复制了QWQ）
题目描述
给定由非负整数组成的n times n的正方形矩阵，你需要寻找一条路径：以左上角为起点,每次只能向右或向下走,以右下角为终点 并且，如果我们把沿路遇到的数进行相乘，积应当是最小“round”，换句话说，应当以最小数目的0的结尾.
输入格式
第一行包含一个整数 (2 leq n leq 1000)，n为矩阵的规模，接下来的n行包含矩阵的元素（不超过10^9的非负整数）.
输出格式
第一行应包含最小尾0的个数，第二行打印出相应的路径（译注：D为下，R为右）
思路
楼下其实说得蛮清楚了，我主要就是说一下坑。。。构成末尾是0的只能是2^a与5^b相乘，所得的0的个数为min(a,b)，所以，只要2、5分别dp一遍，取一下上与左的最小值就好啦。。。最后求路径时递归求一遍就好啦。。。
坑
TLE的小朋友们看这里啦。。。
TLE的小朋友们看这里啦。。。
TLE的小朋友们看这里啦。。。
（重要的事情说三遍）
此题特别会卡时。比如说一开始预处理每个数是2^a与2^b时，需要将此数不间断地除下去，为什么呢？因为卡常数。。。也许时我RP的原因吧。。。卡了半天，终于卡过去了。。。
感谢Seanq提供hack数据：
代码语言：javascript复制3
0 1 1
1 1 1
1 1 1现已添加特判，第一个格子必须要走且第一个格子为0，使得结果为0的情况。感谢Liuyuzhuo提供hack数据：
代码语言：javascript复制3
1 1 1
1 1 1
1 1 0 现已添加特判，最后一个格子如果为0，结果为0。 具体详见代码：
代码
（我知道你要看这个）
代码语言：javascript复制#include<bits/stdc .h>
//#define int long long
using namespace std;//奇丑无比的码风
inline int read(){//cf数据加强，只能加读优了。
int res=0,f=1;char ch=getchar();
while(ch<'0'ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9') res=res*10 ch-'0',ch=getchar();
return res*f;
}
int n,a[1010][1010],f[2][1010][1010],dp[2][1010][1010];
int ans,qx,qy;
bool ff;
inline int get2(register int x,register int y){
if(a[x][y]==0){return 0;} //特判
register int pt=0;
while(a[x][y]%2==0) pt,a[x][y]/=2; //卡常数
return pt;
}
inline int get5(register int x,register int y){
if(a[x][y]==0){return 0;} //特判
register int pt=0;
while(a[x][y]%5==0) pt,a[x][y]/=5; //卡常数
return pt;
}
inline void print(register int k,register int x,register int y,register int first){
if(x==1&&y==1) ;
else if(x==1) print(k,x,y-1,0);
else if(y==1) print(k,x-1,y,1);
else if(dp[k][x][y]==dp[k][x-1][y] f[k][x][y]) print(k,x-1,y,1);
else print(k,x,y-1,0);
if(first==6666) return ;
putchar(first==0?'R':'D'); //一开始在n,n点时不需要输出
return ;
}
signed main(){
n=read();
ff=0;qx=0;qy=0;
for(register int i=1;i<=n;i ){
for(register int j=1;j<=n;j ){
a[i][j]=read();
if(a[i][j]==0){
qx=i;qy=j;
ff=1;
}
}
}
if(a[1][1]==0a[n][n]==0){
puts("1");
for(int i=1;i<=n-1;i ) putchar('D');
for(int i=1;i<=n-1;i ) putchar('R');
return 0;
}
for(register int i=1;i<=n;i ){
for(register int j=1;j<=n;j ){
f[0][i][j]=get2(i,j);
f[1][i][j]=get5(i,j);
}
}
memset(dp,63,sizeof(dp));
for(register int i=1;i<=n;i )
for(register int j=1;j<=n;j ){
dp[0][i][j]=min(dp[0][i][j],dp[0][i-1][j]);
dp[0][i][j]=min(dp[0][i][j],dp[0][i][j-1]);//从左格子与上格子中取最小值
if(i==1&&j==1) dp[0][i][j]=0;
dp[0][i][j] =f[0][i][j];
}
for(register int i=1;i<=n;i )
for(register int j=1;j<=n;j ){
dp[1][i][j]=min(dp[1][i][j],dp[1][i-1][j]);
dp[1][i][j]=min(dp[1][i][j],dp[1][i][j-1]);//从左格子与上格子中取最小值
if(i==1&&j==1) dp[1][i][j]=0;
dp[1][i][j] =f[1][i][j];
}
ans=min(dp[0][n][n],dp[1][n][n]);//初步ans
if(ans>1&&ff==1){ //特判有0的情况，如果有0，那么答案只有0或1.
putchar('1');
putchar('n');
for(register int i=1;i<qx;i ) putchar('D');
for(register int i=1;i<qy;i ) putchar('R');
for(register int i=qx;i<n;i ) putchar('D');
for(register int i=qy;i<n;i ) putchar('R');
putchar('n');
}else{
cout<<ans;
putchar('n');
if(dp[0][n][n]<dp[1][n][n]) print(0,n,n,6666); //分2、5讨论
else print(1,n,n,6666);
putchar('n');
}
return 0;
}
/*
3
0 1 1
1 1 1
1 1 1
*/ 
