Advertisement
Guest User

Untitled

a guest
May 16th, 2018
118
0
Never
Not a member of Pastebin yet? Sign Up, it unlocks many cool features!
C++ 2.02 KB | None | 0 0
  1. #include <bits/stdc++.h>
  2.  
  3. using namespace std;
  4. const int MAXN = 1000 + 10 ;
  5. const int INF = -1u/4 ;
  6. int n ;
  7. int a[MAXN][MAXN][2];
  8. int DP[MAXN][MAXN][2];
  9. vector<char> s ;
  10. bool mee0 ;
  11. int x0,y0;
  12. int main()
  13. {
  14.     cin >> n;
  15.  
  16.     for(int i = 0 ; i < n ; i ++)
  17.         for(int j = 0 ; j < n ; j ++){
  18.             int x;
  19.             scanf("%d",&x);
  20.             if(x == 0){
  21.                 mee0 = true ;
  22.                 a[i][j][0] = a[i][j][1] = INF ;
  23.                 x0 = i ;
  24.  
  25.             }
  26.             else{
  27.                 while(x%2 == 0){
  28.                     x/= 2 ;
  29.                     a[i][j][0] ++;
  30.                 }
  31.                 while(x%5 == 0){
  32.                     x/= 5 ;
  33.                     a[i][j][1] ++ ;
  34.                 }
  35.  
  36.             }
  37.             DP[i][j][0] = DP[i][j][1] = INF ;
  38.  
  39.             for(int t = 0 ; t < 2 ; t ++){
  40.  
  41.                 if(i == 0 && j == 0) {
  42.                     DP[i][j][t] = a[i][j][t];
  43.                     continue ;
  44.                 }
  45.                 if(i != 0) DP[i][j][t] = min (DP[i][j][t] , DP[i-1][j][t]);
  46.                 if(j != 0) DP[i][j][t] = min (DP[i][j][t] , DP[i][j-1][t]);
  47.                 DP[i][j][t] += a[i][j][t];
  48.             }
  49.         }
  50.  
  51.  
  52.     int x ;
  53.  
  54.     if(DP[n-1][n-1][0] < DP[n-1][n-1][1])x = 0 ;
  55.     else x = 1 ;
  56.  
  57.     int nx = n-1 , ny = n-1 ;
  58.  
  59.     if(mee0 && DP[n-1][n-1][x] >= 1){
  60.         cout << "1" <<endl;
  61.  
  62.         for(int i = 0 ; i <x0 ; i ++) printf("D");
  63.         for(int j = 0 ; j < n-1 ; j ++) printf("R");
  64.         for(int i = x0 ; i < n-1 ; i ++ )printf("D");
  65.  
  66.         return 0 ;
  67.     }
  68.  
  69.     while(nx != 0 || ny != 0){
  70.  
  71.         if(nx == 0){ny -- ; s.emplace_back('R')  ; continue ;}
  72.         else if(ny == 0){nx -- ; s.emplace_back('D')  ; continue ;}
  73.         else if(DP[nx-1][ny][x] > DP[nx][ny-1][x]){ny -- ; s.emplace_back('R')  ; continue ;}
  74.         else {nx -- ; s.emplace_back('D')  ; continue ;}
  75.     }
  76.     cout << DP[n-1][n-1][x]<<endl;
  77.     for(int i = s.size()-1 ; i >= 0 ; i --)
  78.            printf("%c",s[i]);
  79. }
Advertisement
Add Comment
Please, Sign In to add comment
Advertisement