动态规划 4.26
CF2B The least round way（数论+dp）
题意：
题目描述
给定由非负整数组成的n×n 的正方形矩阵，你需要寻找一条路径：
以左上角为起点
每次只能向右或向下走
以右下角为终点 并且，如果我们把沿路遇到的数进行相乘，积应当是最小“round”，换句话说，应当以最小数目的0的结尾.
输入格式
第一行包含一个整数 n (2≤n≤1000)，n 为矩阵的规模，接下来的n行包含矩阵的元素（不超过10^9的非负整数）.
输出格式
第一行应包含最小尾0的个数，第二行打印出相应的路径（译注：D为下，R为右）
思路：
结尾包含0的话说明有2和5相乘，那么结尾0的个数为2的个数和5的个数的最小值。
对于每一个数都获取他的因子2和因子5的个数，在看是从左边转移还是上边转移过来更优，记录路径即可。
注意特判的点就是如果该列表有个数为0的话，答案就是经过这个数的路径。
代码：
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
typedef pair<int,int>PII;
#define I_int ll
#define x first
#define y second
#define PI acos(-1)
inline ll read()
{
ll x=0,f=1;char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();}
return x*f;
}
char F[200];
inline void out(I_int x) {
if (x == 0) return (void) (putchar('0'));
I_int tmp = x > 0 ? x : -x;
if (x < 0) putchar('-');
int cnt = 0;
while (tmp > 0) {
F[cnt++] = tmp % 10 + '0';
tmp /= 10;
}
while (cnt > 0) putchar(F[--cnt]);
cout<<endl;
}
const int maxn=2e5+100;
int n,dp[1100][1100][2];
int pre[1100][1100][2],k;
void dfs(int x,int y){
if(x==1&&y==1) return ;
if(pre[x][y][k]){
dfs(x-1,y);
cout<<"D";
}
else{
dfs(x,y-1);
cout<<"R";
}
}
int main(){
cin>>n;
int pos=-1;
for(int i=2;i<=n;i++){
dp[i][0][0]=dp[0][i][0]=0x3f3f3f3f;
dp[0][i][1]=dp[i][0][1]=0x3f3f3f3f;
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
int x;cin>>x;
if(!x){
pos=i;continue;
}
int y=x;
while(y%5==0){
dp[i][j][1]++;
y/=5;
}
y=x;
while(y%2==0){
dp[i][j][0]++;y/=2;
}
}
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++)
for(int k=0;k<2;k++)
if(dp[i-1][j][k]<dp[i][j-1][k]){
dp[i][j][k]+=dp[i-1][j][k];
pre[i][j][k]=1;
}
else{
dp[i][j][k]+=dp[i][j-1][k];
pre[i][j][k]=0;
}
k=0;
if(dp[n][n][0]>dp[n][n][1]) k=1;
if(pos!=-1&&dp[n][n][k]>1){
puts("1");
for(int i=1;i<pos;i++) cout<<"D";
for(int i=1;i<n;i++) cout<<"R";
for(int i=pos;i<n;i++) cout<<"D";
return 0;
}
cout<<dp[n][n][k]<<endl;
dfs(n,n);
return 0;
}