icontofig | 发布于 2019-07-20 09:58:14 | 阅读量 297 | DP 贪心 回溯
发布于 2019-07-20 09:58:14 | DP 贪心 回溯

题目大意

现在给一个n*n的矩阵,你要从(1,1)走到(n,n),求一条路径,使得路径上所有数的乘积的尾部零的个数最少。

题解

我们先考虑尾部零怎么能够产生。

首先要产生尾部零,就一定要乘10或者0。

先来考虑0的情况,如果你走一条带有0的路径的话,那么最后乘积一定会是0,尾部零的数量为1个。

如果我们不走带有0的路径的话,那么要产生尾部0就一定要有因数10,而且有多少个因数10就有多少个尾部零。

而10这个数,很明显的,我们能够将其分解为2*5,由质因数分解的唯一性,我们只需要统计路径上2和5的个数,然后取其中的最少就是最终因数10的个数,也即尾部零的个数。

讨论完尾部0的产生,我们来看一下怎样选择路径。

我们可以先不考虑带0的路径,先来看带质因数2和5的路径。

我们可以用一个三位dp[x][y][0/1]代表走到点(x,y),质因数2/5总共有几个(0和1分别表示选2和选5),然后我们转移方程是很容易写出来的。不过要注意边界,请自行看参考代码。

最后我们得到的dp[n][n][0]和dp[n][n][1]中的最小值就是不考虑带0路径的答案。这里其实是一种贪心思想,由于非常简单十分好理解不再证明(贪心的证明一般都是反证)。

然后我们要看看有没有带0的路径,因为带0的路径尾部零只有1个,所以有可能使答案更小。

我们在DP过程中分别记录选2和选5个数最少的路径(记录从哪个方向来就行了),然后最后进行回溯输出即可。

代码

#include <bits/stdc++.h>
using namespace std;
int get_num(){
    int num = 0;
    char c;
    bool flag = false;
    while((c = getchar()) == ' ' || c == '\r' || c == '\n');
    if(c == '-')
        flag = true;
    else num = c - '0';
    while(isdigit(c = getchar()))
        num = num * 10 + c - '0';
    return (flag ? -1 : 1) * num;
}
int n;
const int maxn = 1005;
int mp[maxn][maxn];
int c;
int dp[maxn][maxn][2];
int xx[maxn][maxn][2];
void work(int x,int y,int k){
    if(x == 1 && y == 1)return;
    if(xx[x][y][k] == 0){
        work(x,y-1,k);
        cout << "R";
    }
    else{
        work(x-1,y,k);
        cout << "D";
    }
    return;
}
int main(){
    n = get_num();
    int flag = 0;
    memset(dp,0,sizeof(dp));
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= n;++j){
            c = get_num();
            mp[i][j] = c;
            if(c == 0){
                flag = i;
                continue;
            }
            while(c % 2 == 0){
                dp[i][j][0]++;
                c /= 2;
            }
            while(c % 5 == 0){
                dp[i][j][1]++;
                c/=5;
            }
        }
    }
    for(int i = 2;i <= n;++i){
        dp[0][i][0] = dp[0][i][1] = 1e9;
        dp[i][0][0] = dp[i][0][1] = 1e9;
    }
    for(int i = 1;i <= n;++i){
        for(int j = 1;j <= n;++j){
            for(int k = 0;k < 2;++k){
                if(dp[i-1][j][k] > dp[i][j-1][k]){
                    dp[i][j][k] += dp[i][j-1][k];
                    xx[i][j][k] = 0;
                }
                else{
                    dp[i][j][k] += dp[i-1][j][k];
                    xx[i][j][k] = 1;
                }
            }
        }
    }
    int k = (dp[n][n][1] > dp[n][n][0]) ? 0 : 1;
    if(flag && dp[n][n][k] > 1){
        cout << 1 << endl;
        for(int l = 2;l <= flag;++l)cout << "D";
        for(int l = 2;l <= n;++l)cout << "R";
        for(int l = flag+1;l <= n;++l)cout << "D";
        cout << endl;
    }
    else{
        cout << dp[n][n][k] << endl;
        work(n,n,k);
        cout << endl;
    }
    return 0;
}



内容更新于: 2019-07-20 09:58:14
链接地址: http://blog.leanote.com/post/icontofig/The-least-round-way

上一篇: HDU 3336 Count the string KMP(瞎搞)

下一篇: 骑士共存问题 [网络流24题] 二分图最大独立集

297 人读过
立即登录, 发表评论.
没有帐号? 立即注册
0 条评论
文档导航