Codeforces Beta Round #2--B题 (DP)

题目：The least round way

1000*1000的方阵，每个格子有一个非负整数，现在要从左上走到右下，每次只能向下或者向右走。目标是使得所有走的格子里的数的乘积里，末尾0的个数最少，要求输出最有解和走法。

不用怎么想也知道基本是个dp了，可以发现其实只有2和5的因子是有用的，但是如果状态同时记录2和5的因子个数的话，就不好表示了。其实方法很简单，对2个5分别做一次，第一次让2尽量少，第二次让5尽量少，两个里面取个最小的就是答案了，应该不难证明。dp过程就比较普通了，记录下路径，最后输出即可，不再赘述。

当然，本题是有一个比较大的trick的，就是如果其中有一个数字为0，那么最后的乘积可以为0，也就是答案至少可以是1。因此，只要先记录下方阵中有没有0，然后dp的时候强制不走0，最后输出走0和不走0的最优解即可。

#include <cstdio>
#include <algorithm>

using namespace std;

const int MAXN = 1024;
int m2[MAXN][MAXN];
int m5[MAXN][MAXN];
int l2[MAXN][MAXN];
int l5[MAXN][MAXN];
int dp2[MAXN][MAXN];
int dp5[MAXN][MAXN];
int n;
int zx, zy;

void output(int ll[MAXN][MAXN], int x, int y)
{
    if (x == 0 && y == 0)
        return;
    if (ll[x][y] == 0)
    {
        output(ll, x - 1, y);
        putchar('D');
    }
    else
    {
        output(ll, x, y - 1);
        putchar('R');
    }
}

int main()
{
    scanf("%d", &n);
    zx = zy = -1;
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            scanf("%d", &m2[i][j]);
            if (m2[i][j] != 0)
            {
                m5[i][j] = 0;
                while (m2[i][j] % 5 == 0)
                {
                    ++m5[i][j];
                    m2[i][j] /= 5;
                }
                int t = 0;
                while (m2[i][j] % 2 == 0)
                {
                    ++t;
                    m2[i][j] /= 2;
                }
                m2[i][j] = t;
            }
            else
            {
                zx = i;
                zy = j;
                m2[i][j] = m5[i][j] = -1;
            }
        }
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (m2[i][j] == -1)
                dp2[i][j] = -1;
            else
            {
                if (i == 0 && j == 0)
                    dp2[i][j] = m2[i][j];
                else
                {
                    dp2[i][j] = 100000000;
                    if (i > 0 && dp2[i - 1][j] != -1 && dp2[i - 1][j] + m2[i][j] < dp2[i][j])
                    {
                        dp2[i][j] = dp2[i - 1][j] + m2[i][j];
                        l2[i][j] = 0;
                    }
                    if (j > 0 && dp2[i][j - 1] != -1 && dp2[i][j - 1] + m2[i][j] < dp2[i][j])
                    {
                        dp2[i][j] = dp2[i][j - 1] + m2[i][j];
                        l2[i][j] = 1;
                    }
                    if (dp2[i][j] == 100000000)
                        dp2[i][j] = -1;
                }
            }
        }
    }
    for (int i = 0; i < n; ++i)
    {
        for (int j = 0; j < n; ++j)
        {
            if (m5[i][j] == -1)
                dp5[i][j] = -1;
            else
            {
                if (i == 0 && j == 0)
                    dp5[i][j] = m5[i][j];
                else
                {
                    dp5[i][j] = 100000000;
                    if (i > 0 && dp5[i - 1][j] != -1 && dp5[i - 1][j] + m5[i][j] < dp5[i][j])
                    {
                        dp5[i][j] = dp5[i - 1][j] + m5[i][j];
                        l5[i][j] = 0;
                    }
                    if (j > 0 && dp5[i][j - 1] != -1 && dp5[i][j - 1] + m5[i][j] < dp5[i][j])
                    {
                        dp5[i][j] = dp5[i][j - 1] + m5[i][j];
                        l5[i][j] = 1;
                    }
                    if (dp5[i][j] == 100000000)
                        dp5[i][j] = -1;
                }
            }
        }
    }
    if (dp2[n - 1][n - 1] == -1)
    {
        printf("1\n");
        for (int i = 0; i < n - 1; ++i)
            putchar('D');
        for (int i = 0; i < n - 1; ++i)
            putchar('R');
        puts("");
    }
    else
    {
        int now = min(dp2[n - 1][n - 1], dp5[n - 1][n - 1]);
        if (zx != -1 && now >= 1)
        {
            printf("1\n");
            for (int i = 0; i < zx; ++i)
                putchar('D');
            for (int i = 0; i < n - 1; ++i)
                putchar('R');
            for (int i = zx; i < n - 1; ++i)
                putchar('D');
            puts("");
        }
        else
        {
            printf("%d\n", now);
            if (dp2[n - 1][n - 1] < dp5[n - 1][n - 1])
                output(l2, n - 1, n - 1);
            else
                output(l5, n - 1, n - 1);
            puts("");
        }
    }
    return 0;
}