【Codeforces】CF 2 B The least round way（dp）

题目

传送门：QWQ

分析

求结尾0的数量QwQ。

10只能是$ 2 \times 5 $，我们预处理出每个数因子中2和5的数量。

我们接着dp出从左上到右下的经过的最少的2的数量和最少的5的数量。两者取min后就是答案。

特判数据中有0的情况，把他当做10处理。如果此时答案大于1，那么把答案更新成1。因为0只有1个0。

输出也有些小技巧

代码

 #include <bits/stdc++.h>

 using namespace std;

 const int maxn=;

 int a[maxn][maxn][], dp[maxn][maxn][];

 void print(int x,int y,int k,int state){

     if(x<= || y<=) return;

     if(dp[x-][y][k]==dp[x][y][k]-a[x][y][k]) print(x-,y,k,);

     else print(x,y-,k,);

     if(state==) return;

     if(state==) putchar('R');

     else putchar('D');

 }

 int main(){

     int n, posx, posy, flag=;

     scanf("%d",&n);

     for(int i=;i<=n;i++) {

         for(int j=;j<=n;j++) {

             int num; scanf("%d",&num);

             if(!num) {

                 posx=i;posy=j; flag=;

                 a[i][j][]=a[i][j][]=; continue;

             }

             while(num%==) a[i][j][]++,num/=;

             while(num%==) a[i][j][]++,num/=;

         }

     }

     memset(dp,,sizeof(dp));

     dp[][][]=dp[][][] =;

     for(int i=;i<=n;i++){

         for(int j=;j<=n;j++){

             for(int k=;k<;k++){

                 dp[i][j][k] = min (min(dp[i][j-][k],dp[i-][j][k]), dp[i][j][k]) + a[i][j][k];

             }

         }

     }

     int ans=min(dp[n][n][],dp[n][n][]);

     if(flag && ans>){

         printf("%d\n",);

         for(int i=;i<posx;i++) putchar('D');

         for(int i=;i<posy;i++) putchar('R');

         for(int i=posx+;i<=n;i++) putchar('D');

         for(int i=posy+;i<=n;i++) putchar('R');

         return ;

     }

     printf("%d\n",ans);

     if(dp[n][n][] > dp[n][n][]) print(n,n,,);

     else print(n,n,,);

     return ;

 }