数论+dp Codeforces Beta Round #2 B

时间：2023-03-09 02:48:32
数论+dp Codeforces Beta Round #2 B

http://codeforces.com/contest/2/problem/B

题目大意：给你一个n*n的矩形，问从(1,1)出发到(n,n)，把图中经过的所有的数字都乘在一起，最后这个数字有多少个0？

思路：经过分析，只有2和5出现的时候才会有0.所以我们预处理把这个数包含的所有的2和5都给拿出来就好了。但是我发现如果每次转移都要统计2和5的个数的话，状态就炸了，所以我只想到了这里TAT。后来看了一下题解以后发现，只需要知道目前到这个位置以后最小的2（或5）的个数就好了。

然后转移我也想了好半天。。。于是还是看了。。。2333（我好菜啊）

转移就是只需要知道最后最小的个数是2还是5，然后再通过该数字去转移就好了

于是早上+中午+下午3个小时就过去了= =

//看看会不会爆int!数组会不会少了一维！

//取物问题一定要小心先手胜利的条件

#include <bits/stdc++.h>

using namespace std;

#define LL long long

#define ALL(a) a.begin(), a.end()

#define pb push_back

#define mk make_pair

#define fi first

#define se second

#define haha printf("haha\n")

const int maxn =  + ;

const LL inf = 1e17;

LL a[maxn][maxn];

pair<LL, LL> p[maxn][maxn];

LL dp[maxn][maxn][];

int n;

/*

定义dp[i][j]表示到（i，j）所经过的0的最少的个数

0只在2*5的时候出现，所以只需要统计2和5的个数即可

以上思路是行不通的，因为这样子的话dfs或者dp都会有两个变量，所以会超级难写(TAT我写了一个早上)

所以我们要找一下两者当中的共同点。我们只需要找目前状态的2或5的最大值就好了

*/

pair<LL, LL> cal(LL val){

    pair<LL, LL> cnt = mk(, );

    LL tmp = val;

    while (val %  ==  && val) {cnt.fi++; val /= ;}

    val = tmp;

    while (val %  ==  && val) {cnt.se++; val /= ;}

    return cnt;

}

vector<char> v;

bool dfs(int x, int y, int k){///0 is first, 1 is second

    //printf("x = %d y = %d\n", x, y);

    if (x > n || y > n || x <  || y < ) return false;

    if (x ==  && y == ) return true;

    if (dp[x - ][y][k] < dp[x][y - ][k]){

        if (dfs(x - , y, k)) {v.push_back('D'); return true;}

    }

    else {

        if (dfs(x, y - , k)) {v.push_back('R'); return true;}

    }

    return false;

}

int main(){

    cin >> n;

    memset(p, -, sizeof(p));

    bool flag = false;

    pair<int, int> zero;

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

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

            scanf("%lld", &a[i][j]);

            p[i][j] = cal(a[i][j] ==  ?  : a[i][j]);///当做10,先消去0的影响

            if (a[i][j] == ) {flag = true; zero = mk(i, j);}

        }

    }

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

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

            for (int k = ; k < ; k++)

                dp[i][j][k] = inf;

            if (p[i][j].fi == -) p[i][j] = mk(inf, inf);

        }

    dp[][][] = p[][].fi, dp[][][] = p[][].se;

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

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

            if (i ==  && j == ) continue;

            dp[i][j][] = min(dp[i - ][j][], dp[i][j - ][]) + p[i][j].fi;

            dp[i][j][] = min(dp[i - ][j][], dp[i][j - ][]) + p[i][j].se;

        }

    }

/*

    haha;

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

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

            printf("%lld%c", min(dp[i][j][0], dp[i][j][1]), j == n ? '\n' : ' ');

*/

    LL ans = min(dp[n][n][], dp[n][n][]);

    if (flag && ans >= flag){

        ans = 1LL * flag;

        printf("%lld\n", ans);

        int cnt = ;

        for (int i = ; i <= zero.fi; i++) printf("D"), cnt++;

        for (int i = ; i < n; i++) printf("R"), cnt++;

        for (int i = zero.fi + ; i<= n; i++) printf("D"), cnt++;

        cout << endl;

        return ;

    }

    printf("%lld\n", ans);

    dfs(n, n, dp[n][n][] > dp[n][n][]);

    for (int i = ; i < v.size(); i++)

        printf("%c", v[i]);

    cout << endl;

    return ;

}

/*

4

1 10 10 10

1  0  1 10

10 10 2 10

1  10 1 1

*/

相关文章