algorithm - 我将如何使用 DP 解决这个问题？

Question

提问链接:http://codeforces.com/contest/2/problem/B

有一个方阵n⟩×⟩n，由非负整数组成。你应该在上面找到这样的方法

从矩阵的左上角单元格开始； 每个后续单元格都在当前单元格的右侧或下方； 这条路在右下角的单元格结束。 此外，如果我们将一路上的所有数字相乘，结果应该是最不“圆”的。换句话说，它应该以尽可能少的零结尾。

输入 第一行包含一个整数n(2⟩≤⟩n⟩≤⟩1000)，n是矩阵的大小。然后是包含矩阵元素(不超过 10^9 的非负整数)的 n 行。

输出 在第一行打印最少数量的尾随零。在第二行打印通讯方式本身。

我想到了以下几点:最后，无论答案是什么，它都应该包含 2 和 5 的最小次方。因此，我所做的是，对于输入矩阵中的每个条目，我计算了 2 和 5 的幂并将它们存储在单独的矩阵中。

    for (i = 0; i < n; i++)
    {
        for ( j = 0; j < n; j++)
        {
            cin>>foo;
            matrix[i][j] = foo;
            int n1 = calctwo(foo);   // calculates the number of 2's in factorisation of that number
            int n2 = calcfive(foo); // calculates number of 5's
            two[i][j] = n1;
            five[i][j] = n2;
        }
    }

之后，我这样做了:

for (i = 0; i < n; i++)
{
    for ( j = 0; j < n; j++ )
    {
        dp[i][j] = min(two[i][j],five[i][j]);  // Here, dp[i][j] will store minimum number of 2's and 5's. 
    }
}

但以上并不是一个有效的答案，我不知道为什么？我是否实现了正确的方法？或者，这是解决这个问题的正确方法吗？

编辑:这是我计算一个数中二的个数和五的个数的函数。

int calctwo (int foo)
{
    int counter = 0;
    while (foo%2 == 0)
    {
        if (foo%2 == 0)
        {
            counter++;
            foo = foo/2;
        }
        else
            break;
    }
    return counter;
}

int calcfive (int foo)
{
    int counter = 0;
    while (foo%5 == 0)
    {
        if (foo%5 == 0)
        {
            counter++;
            foo = foo/5;
        }
        else
            break;
    }
    return counter;
}

Edit2:链接中给出的 I/O 示例:

输入:

3
1 2 3
4 5 6
7 8 9

输出:

0
DDRR

Answer 1

由于您只对尾随零的数量感兴趣，因此只需考虑 2 的幂, 5你可以把它分成两个独立的nxn阵列。所以对于数组

1 2 3
4 5 6
7 8 9

你只需要保留数组

the powers of 2    the powers of 5       
0 1 0              0 0 0
2 0 1              0 1 0
0 3 0              0 0 0

问题的见解如下。请注意，如果您找到使 2 的幂之和最小的路径和使 5 的幂之和最小的路径，那么答案就是这两条路径中具有较低值的路径。因此，您将问题简化为以下经典 dp 问题的两次应用:找到一条路径，从左上角开始到右下角结束，使其元素之和最小。同样，按照示例，我们有:

 minimal path for the 
 powers of 2                 value
 * * -                         2
 - * * 
 - - *

 minimal path for the 
 powers of 5                 value
 * - -                         0
 * - - 
 * * *

所以你的答案是

 * - -                      
 * - - 
 * * *

值(value)0

注1

似乎采用两条最优路径中的最小值只给出了一个上限，因此可能会出现一个问题:这个界限是否真的达到了？答案是肯定的。为方便起见，令 2 的最优路径上的 2 的个数为 a并且 5 的最佳路径上 5 的数量是 b .在不失一般性的情况下，假设两条最佳路径中的最小值是 2 的幂(即 a < b )。令最小路径上 5 的个数为 c .现在的问题是:沿着这条路径有 5 个和 2 个一样多(即是 c >= a 吗？)。假设答案是否定的。这意味着沿着最小路径(即 c < a )，5 的数量少于 2 的数量。由于 5 的路径的最佳值为 b我们有每个 5 的路径至少有 b里面有5个。对于最小路径也应该如此。这意味着 c > b .我们有c < a所以a > b但最初的假设是 a < b .自相矛盾。

注2

您可能还想考虑元素 0 的情况在你的矩阵中。我假设乘积为 1 时尾随零的数量。在这种情况下，如果算法产生的结果的值大于 1，则应输出 1 并打印一条通过元素 0 的路径。 .