[CF2B] The least round way

给定由非负整数组成的n×n 的正方形矩阵，你需要寻找一条路径：

以左上角为起点

每次只能向右或向下走

以右下角为终点并且，如果我们把沿路遇到的数进行相乘，积应当是最小“round”，换句话说，应当以最小数目的0的结尾.

Solution

考虑到最终答案只取决于 \(2,5\) 因子数中最小的那一个，所以可以拆开考虑，然后就是一个朴素的最小和路径dp了

注意如果原矩阵中包含零，答案要和 \(1\) 取 min 一下

#include <bits/stdc++.h>

using namespace std;

vector <int> pat;

int n,a[1005][1005],x[1005][1005],f[1005][1005],ans=1e+9;

void solve(int p) {

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

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

            a[i][j]=0;

            int t=x[i][j];

            while(t && t%p==0) t/=p, a[i][j]++;

        }

    }

    memset(f,0x3f,sizeof f);

    f[0][1]=0;

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

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

            f[i][j]=min(f[i-1][j],f[i][j-1])+a[i][j];

        }

    }

    /*for(int i=1;i<=n;i++) {

        for(int j=1;j<=n;j++) cout<<f[i][j]<<" ";

        cout<<endl;

    }*/

    vector <int> v;

    {

    int p=n,q=n;

    while(p!=1 && q!=1) {

        int i=p, j=q;

        if(f[i][j]==f[i-1][j]+a[i][j]) {

            v.push_back(1); //cout<<"up";

            --p;

        }

        else if(f[i][j]==f[i][j-1]+a[i][j]) {

            v.push_back(0); //cout<<"left";

            --q;

        }

        else cout<<"err";

    }

    while(p!=1) {

        --p;

        v.push_back(1);

    }

    while(q!=1) {

        --q;

        v.push_back(0);

    }

    reverse(v.begin(),v.end());

    if(f[n][n]<ans) {

        ans=f[n][n];

        pat=v;

    }

    }

}

int main() {

    scanf("%d",&n);

    int flag=0,posx,posy;

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

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

            scanf("%d",&x[i][j]);

            if(x[i][j]==0) flag=1,posx=i,posy=j;

        }

    }

    solve(2);

    solve(5);

    if(ans>1 && flag) {

        cout<<1<<endl;

        for(int i=1;i<posx;i++) cout<<"D";

        for(int i=1;i<posy;i++) cout<<"R";

        for(int i=posx;i<n;i++) cout<<"D";

        for(int i=posy;i<n;i++) cout<<"R";

        return 0;

    }

    cout<<ans<<endl;

    for(int i=0;i<pat.size();i++) {

        cout<<(pat[i]?"D":"R");

    }

}

巴特西

[CF2B] The least round way - dp

Solution

最新文章

热门文章