B. The least round way

题目链接

Codeforces Beta Round #2--B. The least round way

题解

简单题。题意大概是从左上移动到右下,每次只能向右或向下移动,求路径上所有数字之奇后缀0数目最少的走法。
首先将所有元素分解出2和5的因数,找出因数2的数目和因数5的数目中最少的路径,在dp的同时记录转移方向即可。注意,如果出现0需要特判。

代码

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1005;
int n;
int input2[MAXN][MAXN];
int input5[MAXN][MAXN];
int min2[MAXN][MAXN];
int dir2[MAXN][MAXN];
int min5[MAXN][MAXN];
int dir5[MAXN][MAXN];//1==l,2==t,3==l+t;
int q1,q2,maxnum;
bool flag;
int flagx,flagy;
int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);
    cin>>n;
    for(int i=1;i<=n;i++){
        for (int j=1;j<=n;j++){
            cin>>q1;
            if (q1==0){
                flag=true;
                flagy=i;
                flagx=j;
                input2[i][j]=1;
                input5[i][j]=1;
                continue;
            }
            maxnum=max(maxnum,q1);
            q2=q1;
            while(q1%2==0&&q1){
                input2[i][j]++;
                q1/=2;
            }
            while(q2%5==0&&q2){
                input5[i][j]++;
                q2/=5;
            }
        }
    }
    if (maxnum==0){
        cout<<1<<endl;
        return 0;
    }
    min2[1][1]=input2[1][1];
    min5[1][1]=input5[1][1];
    for (int i=2;i<=n;i++){
        dir2[1][i]=1;
        dir5[1][i]=1;
        dir2[i][1]=2;
        dir5[i][1]=2;
        min2[1][i]=min2[1][i-1]+input2[1][i];
        min5[1][i]=min5[1][i-1]+input5[1][i];
        min2[i][1]=min2[i-1][1]+input2[i][1];
        min5[i][1]=min5[i-1][1]+input5[i][1];
    }
    for (int i=2;i<=n;i++){
        for(int j=2;j<=n;j++){
            if (min2[i][j-1]==min2[i-1][j]){
                min2[i][j]=input2[i][j]+min2[i][j-1];
                dir2[i][j]=3;
            }
            else if(min2[i][j-1]<min2[i-1][j]){
                min2[i][j]=input2[i][j]+min2[i][j-1];
                dir2[i][j]=1;
            }
            else if(min2[i][j-1]>min2[i-1][j]){
                min2[i][j]=input2[i][j]+min2[i-1][j];
                dir2[i][j]=2;
            }
            if (min5[i][j-1]==min5[i-1][j]){
                min5[i][j]=input5[i][j]+min5[i][j-1];
                dir5[i][j]=3;
            }
            else if(min5[i][j-1]<min5[i-1][j]){
                min5[i][j]=input5[i][j]+min5[i][j-1];
                dir5[i][j]=1;
            }
            else if(min5[i][j-1]>min5[i-1][j]){
                min5[i][j]=input5[i][j]+min5[i-1][j];
                dir5[i][j]=2;
            }
        }
    }
    if (min(min2[n][n],min5[n][n])>=1&&flag){
        cout<<1<<endl;
        for (int i=1;i<flagy;i++){
            cout<<'D';
        }
        for (int i=1;i<flagx;i++){
            cout<<'R';
        }
        for (int i=flagy;i<n;i++){
            cout<<'D';
        }
        for (int i=flagx;i<n;i++){
            cout<<'R';
        }
    }
    else if (min2[n][n]<=min5[n][n]){

        cout<<min2[n][n]<<endl;
        stack<char>ans;
        int posx(n),posy(n);
        while(!(posx==1&&posy==1)){
            if (dir2[posy][posx]==2){
                ans.push('D');
                posy--;
            }
            else {
                ans.push('R');
                posx--;
            }
        }
        for (int i=1;i<=n*2-2;i++){
            cout<<ans.top();
            ans.pop();
        }
    }
    else {
        cout<<min5[n][n]<<endl;
        stack<char>ans;
        int posx(n),posy(n);
        while(!(posx==1&&posy==1)){
            if (dir5[posy][posx]==2){
                ans.push('D');
                posy--;
            }
            else {
                ans.push('R');
                posx--;
            }
        }
        for (int i=1;i<=n*2-2;i++){
            cout<<ans.top();
            ans.pop();
        }
    }
}

标签: math, dp

添加新评论