题目出处:http://codeforces.com/problemset/problem/2/B

题目描述

给你一个 \(n \times n\) 的二维数组,它包含的元素都是非负整数。你需要寻找一条满足如下条件的行走路线:

  • 这条路线的起始位置在二维数组的左上角;
  • 每一步你只可以从当前的位置往右或者往下走一格;
  • 这条路线的终止位置在二维数组的右下角。

此外,如果我们一路上把所有的数字相乘,结果应该是最不“圆”的。换句话说,这个乘积结尾的 \(0\) 应该尽可能地少。

输入格式

输入的第一行包含一个整数 \(n(2 \le n \le 1000)\) ,用于表示二维数组的大小。
接下来 \(n\) 行,每行包含 \(n\) 个元素用于表示这个二维数组(数据保证二维数组的每个元素都是非负整数并且不超过 \(10^9\) )。

输出格式

输出的第一行包含一个整数,用于表示最不圆路线的结尾 \(0\) 的个数。
输出的第二行用于表述路线(具体表述方式见样例输出,一个字符 'R' 表示向右走一格,一个字符 'D' 表示向下走一格)。

样例输入

3
1 2 3
4 5 6
7 8 9

样例输出

0
DDRR

题目分析

本题涉及算法:动态规划。
接下来我们来正式将解题思路:
我们设左上角坐标为 \((0,0)\) ,右下角坐标为 \((n-1,n-1)\) ,同时我们设:

  • \(a[i][j]\) :表示数组第 \(i\) 行第 \(j\) 列的元素;
  • \(num2[i][j]\) :表示 \(a[i][j]\) 最多能分解出的 \(2\) 的数量;
  • \(num5[i][j]\) :表示 \(a[i][j]\) 最多能分解出的 \(5\) 的数量;
  • \(f2[i][j]\) :表示从左上角 \((0,0)\) 走到 \((i,j)\) 的路线上所有数的乘积中包含的最少的 \(2\) 的数量;
  • \(f5[i][j]\) :表示从左上角 \((0,0)\) 走到 \((i,j)\) 的路线上所有数的乘积中包含的最少的 \(5\) 的数量。

然后我们可以根据 \(f2[n-1][n-1]\)\(f5[n-1][n-1]\) 的大小来确定路线:

  • 如果 \(f2[n-1][n-1] \le f5[n-1][n-1]\) ,那我从 \((n-1,n-1)\)\((0,0)\) 能够逆推出一条得到 \(f2[n-1][n-1]\) 的路线,我在一般情况下就是我们的答案;
  • 如果 \(f2[n-1][n-1] > f5[n-1][n-1]\) ,那我从 \((n-1,n-1)\)\((0,0)\) 能够逆推出一条得到 \(f5[n-1][n-1]\) 的路线,我在一般情况下就是我们的答案。

注意,这里我说的是“一般情况”,那么什么是非一般情况呢,那就是存在一个元素为 \(0\) 的情况,那么这个时候又同时满足 \(min(f2[n-1][n-1] , f5[n-1][n-1]) > 1\) ,那么我们就不应该通过 \(f2\) 或者 \(f5\) 去逆推了,而是只需要找一条经过这个数值为 \(0\) 的位置的路线就可以了。
实现代码如下:

#include <bits/stdc++.h>
using namespace std;
const int maxn = 1010;
int n, a[maxn][maxn], num2[maxn][maxn], num5[maxn][maxn], f2[maxn][maxn], f5[maxn][maxn];
stack<char> res;
void output(int f[][maxn]) {
    cout << f[n-1][n-1] << endl;
    int r = n-1, c = n-1;
    while (r && c) {
        if (f[r-1][c] <= f[r][c-1]) { res.push('D'); r--; }
        else { res.push('R'); c --; }
    }
    while (r) { res.push('D'); r --; }
    while (c) { res.push('R'); c --; }
    while (!res.empty()) {
        putchar(res.top());
        res.pop();
    }
}
int main() {
    cin >> n;
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++) {
            cin >> a[i][j];
            while (a[i][j] > 0 && a[i][j] % 2 == 0) {
                a[i][j] /= 2;
                num2[i][j] ++;
            }
            while (a[i][j] > 0 && a[i][j] % 5 == 0) {
                a[i][j] /= 5;
                num5[i][j] ++;
            }
        }
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++) {
            if (i == 0 && j == 0) {
                f2[i][j] = num2[i][j];
                f5[i][j] = num5[i][j];
            }
            else if (i == 0) {
                f2[i][j] = f2[i][j-1] + num2[i][j];
                f5[i][j] = f5[i][j-1] + num5[i][j];
            }
            else if (j == 0) {
                f2[i][j] = f2[i-1][j] + num2[i][j];
                f5[i][j] = f5[i-1][j] + num5[i][j];
            }
            else {
                f2[i][j] = min(f2[i-1][j], f2[i][j-1]) + num2[i][j];
                f5[i][j] = min(f5[i-1][j], f5[i][j-1]) + num5[i][j];
            }
        }
    int r0 = -1, c0 = -1;
    for (int i = 0; i < n; i ++)
        for (int j = 0; j < n; j ++)
            if (a[i][j] == 0) {
                r0 = i; c0 = j;
            }
    if (r0 != -1 && min(f2[n-1][n-1], f5[n-1][n-1]) > 1) {  // 如果存在数值为0且f2,f5较小值>1
        int r = 0, c = 0;
        cout << 1 << endl;
        while (c < c0) { putchar('R'); c ++; }
        while (r < r0) { putchar('D'); r ++; }
        while (c < n-1) { putchar('R'); c ++; }
        while (r < n-1) { putchar('D'); r ++; }
    }
    else
        output(f2[n-1][n-1] <= f5[n-1][n-1] ? f2 : f5);
    return 0;
}
01-06 01:56