CodeForces - 2B The least round way

Posted on | In , ,

思路

CCPC比赛的时候感觉自己dp实在太差了，最近准备补一波
本题的意思是从一个矩阵的左上角走到右下角（只能向右和向下），问路径上数的积的末尾最少有几个零。我们可以想到把2和5分开考虑，分别dp然后看右下角是2少还是5少，然后回溯打印路径。需要注意的是当矩阵中有0时，我们要考虑如果我们右下角能得到一个一个末尾0都没有的数的话，我们选这种方案，不然经过0的路径一定是最优的（末尾只有一个0）。
转移方程：
dp1[i][j]=min(dp1[i-1][j],dp1[i][j-1])+two[i][j];
dp2[i][j]=min(dp2[i-1][j],dp2[i][j-1])+five[i][j];

代码

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <bits/stdc++.h>
#define ll long long
#define INF 1e9
#define ms(a,val) memset((a),(val),(sizeof(a)))
#pragma comment(linker, "/STACK:102400000,102400000")

using namespace std;

int a[1005][1005],two[1005][1005],five[1005][1005],dp1[1005][1005],dp2[1005][1005];
int main(){
    int n;
    while(~scanf("%d",&n)){
        int flag=0,x,y;
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                dp1[i][j]=dp2[i][j]=INF;
            }
        }
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                scanf("%d",&a[i][j]);
                if(a[i][j]==0)flag=1,x=i,y=j;
                int temp1,temp2;
                temp1=temp2=a[i][j];
                if(temp1>0&&temp1%2==0){
                    while(temp1%2==0){
                        two[i][j]++;
                        temp1/=2;
                    }
                }
                if(temp2>0&&temp2%5==0){
                    while(temp2%5==0){
                        five[i][j]++;
                        temp2/=5;
                    }
                }
            }
        }
        dp1[0][0]=two[0][0],dp2[0][0]=five[0][0];
        for(int i=0;i<n;i++){
            for(int j=0;j<n;j++){
                if(i>0){
                    dp1[i][j]=min(dp1[i][j],dp1[i-1][j]+two[i][j]);
                    dp2[i][j]=min(dp2[i][j],dp2[i-1][j]+five[i][j]);
                }
                if(j>0){
                    dp1[i][j]=min(dp1[i][j],dp1[i][j-1]+two[i][j]);
                    dp2[i][j]=min(dp2[i][j],dp2[i][j-1]+five[i][j]);
                }
            }
        }
        if(flag&&(dp1[n-1][n-1]>1&&dp2[n-1][n-1]>1)){
            printf("1\n");
            for(int i=0;i<x;i++)printf("D");
            for(int i=0;i<n-1;i++)printf("R");
            for(int i=x;i<n-1;i++)printf("D");
            printf("\n");
        }
        else{
            char cmd[2005];
            if(dp1[n-1][n-1]<dp2[n-1][n-1]){
                printf("%d\n",dp1[n-1][n-1]);
                int ind=2*n-3,i=n-1,j=n-1;
                cmd[2*n-2]='\0';
                while(ind>=0){
                    if(i>0&&dp1[i-1][j]+two[i][j]==dp1[i][j])cmd[ind]='D',i--;
                    else if(j>0) cmd[ind]='R',j--;
                    ind--;
                }
            }
            else{
                printf("%d\n",dp2[n-1][n-1]);
                int ind=2*n-3,i=n-1,j=n-1;
                cmd[2*n-2]='\0';
                while(ind>=0){
                    if(i>0&&dp2[i-1][j]+five[i][j]==dp2[i][j])cmd[ind]='D',i--;
                    else if(j>0)cmd[ind]='R',j--;
                    ind--;
                }
            }
            printf("%s\n",cmd);
        }
    }
    return 0;
}