codeforces 2B 动态规划

淡淡的烟草味﹌ 2022-07-24 06:26 159阅读 0赞

B. The least round way

time limit per test

5 seconds

memory limit per test

64 megabytes

input

standard input

output

standard output

There is a square matrix *n* × *n*, consisting of non-negative integer numbers. You should find such a way on it that

*  starts in the upper left cell of the matrix;
 *  each following cell is to the right or down from the current cell;
 *  the way ends in the bottom right cell.

Moreover, if we multiply together all the numbers along the way, the result should be the least "round". In other words, it should end in the least possible number of zeros.

Input

The first line contains an integer number *n* (2 ≤ *n* ≤ 1000), *n* is the size of the matrix. Then follow *n* lines containing the matrix elements (non-negative integer numbers not exceeding 109).

Output

In the first line print the least number of trailing zeros. In the second line print the correspondent way itself.

Examples

input

3
    1 2 3
    4 5 6
    7 8 9

output

0
    DDRR

题意:

从左上角到右下角, 每次只能往右或者往下走, 求所经过的路径中所有数相乘得到的结果末尾0最少的个数是多少, 并且吧路径输出.

分析:

求末尾的0的个数, 肯定是与原先的数中2的个数和5的个数有关, 我们先把原先的数中2的个数和5的个数记录下来, 然后两次dp,分别求出从左上角到右下角2的个数的最小值和5的个数的最小值; 两者取最小值就是答案, 同时在dp的过程中记录路径. 然后有一点需要注意的是有0的情况我们要特判, 先把0当成10来处理, 跑两遍dp, 如果最后的结果是0, 说明可以不经过0这条路径, 如果结果大于等于1, 那么只需要把0这条路径输出就行了.

#include<bits/stdc++.h>
    
    #define inf 0x3f3f3f3f
    using namespace std;
    
    typedef long long ll;
    typedef pair<int,int> pii;
    
    const int N=1010,MOD=1e9+7;
    int a[N][N];
    int dp[N][N];
    int path[N][N][2],two[N][N],five[N][N];
    
    int main()
    {
        int n;
        scanf("%d",&n);
        int zero=0,x1,y1;
        for(int i=1;i<=n;i++){
            for(int j=1;j<=n;j++){
                int cnt=0;
                scanf("%d",&a[i][j]);
                int t=a[i][j];
                if(t==0){
                     t=10,zero=1;  //把0当成10来处理
                     x1=i,y1=j;
                }
                while(t%2==0) t>>=1,cnt++;
                two[i][j]=cnt;
                cnt=0;
                while(t%5==0) t/=5,cnt++;
                five[i][j]=cnt;
            }
        }
        //边界特殊处理
        for(int i=1;i<=n;i++) two[1][i] += two[1][i-1],five[1][i] += five[1][i-1];
        for(int i=1;i<=n;i++) two[i][1] += two[i-1][1],five[i][1] += five[i-1][1];
        for(int i=1;i<=n;i++) path[i][1][0] = path[i][1][1] = 1,path[1][i][0] = path[1][i][1] = 2; 
    
        for(int i=2;i<=n;i++){
            for(int j=2;j<=n;j++){
                int t1 = two[i][j],t2=five[i][j];
                if(i-1)
                {
                    two[i][j] = two[i-1][j] + t1;
                    path[i][j][0] = 1; //up
                }
                if(j-1 && two[i][j] > two[i][j-1] + t1)
                {
                    two[i][j] = two[i][j-1] + t1;
                    path[i][j][0] = 2; //right
                }
                if(i-1)
                {
                    five[i][j] = five[i-1][j] + t2;
                    path[i][j][1] = 1; //up
                }
                if(j-1 && five[i][j] > five[i][j-1] + t2)
                {
                    five[i][j] = five[i][j-1] + t2;
                    path[i][j][1] = 2; //right
                }
            }
        }
        int f=0;
        if(two[n][n] >= five[n][n]) f=1;
        int ret = min(two[n][n],five[n][n]);
        if(zero && ret>=1){ //选择经过0的路径
            puts("1");
            int t1=n-x1,t2=n-y1;
            x1--,y1--;
            while(y1--) putchar('R');
            while(x1--) putchar('D');
            while(t1--) putchar('D');
            while(t2--) putchar('R');
            return 0;
        }
    //    cout<<"f=="<<f<<endl;
    //    for(int i=1;i<=n;i++){
    //        for(int j=1;j<=n;j++){
    //            printf("%d ",path[i][j][f]);
    //        }
    //        puts("");
    //    }
        printf("%d\n",ret);
        int x=n,y=n;
        vector<char> ans;
        while(x!=1 || y!=1)
        {
    
            if(path[x][y][f] == 1) ans.push_back('D'),x--;
            else ans.push_back('R'),y--;
        }
        reverse(ans.begin(),ans.end());
        for(int i=0;i<ans.size();i++){
            putchar(ans[i]);
        }
        return 0;
    }