方格取數_紀中_dp

Description

　　給定一個N*M的矩陣，記錄左上角為(1,1)，右下角為(N,M)，現在從(1,1)開始取數，每次隻能向下或向右移動一個機關，最終到達(N,M)，我們把路徑上所有的數相乘，記為C。使C的結果最大已經不能滿足我們了，現在我們想讓C末尾的零最少。

　　Ps.11000末尾有3個零，100000100末尾有2個零。

　　

Input

　　輸入檔案matrix.in的第一行包含兩個正整數N，M表示矩陣大小。

　　接下來N行每行M個正整數給出整個矩陣。

Output

　　輸出檔案名為matrix.out。包含一個整數表示所求最小值。

　　

Hint

[資料規模和約定]

　　30%的資料滿足 N , M ≤ 5；

　　100%的資料滿足 1 < N , M ≤ 1000，所有輸入資料不超過32位整範圍。

思路

兩數相乘末尾增加零的情況隻有2*5，統計格子裡數字因數分别為2和5的數量裝兩個數組，dp求一條左上通往右下的路徑和

f[i][j]=minf[i−1][j],f[i][j−1]

code

#include <stdio.h>
#include <cstring>
using namespace std;
int map[][];
int a[][],b[][],f[][];
int min(int x,int y)
{
    return x<y?x:y;
}
int count(int x,int v)
{
    int tmp=;
    while (x%v==)
    {
        x/=v;
        tmp++;
    }
    return tmp;
}
int main()
{
    int n,m;
    scanf("%d%d",&n,&m);
    for (int i=;i<=n;i++)
        for (int j=;j<=m;j++)
            f[i][j]=<<-;
    f[][]=;
    f[][]=;

    for (int i=;i<=n;i++)
        for (int j=;j<=m;j++)
            scanf("%d",&map[i][j]);

    for (int i=;i<=n;i++)
        for (int j=;j<=m;j++)
        {
            a[i][j]=count(map[i][j],);
            b[i][j]=count(map[i][j],);
        }

    for (int i=;i<=n;i++)
        for (int j=;j<=m;j++)
            f[i][j]=a[i][j]+min(f[i-][j],f[i][j-]);

    int ans_A=f[n][m];

    for (int i=;i<=n;i++)
        for (int j=;j<=m;j++)
            f[i][j]=b[i][j]+min(f[i-][j],f[i][j-]);

    int ans_B=f[n][m];

    printf("%d\n",min(ans_A,ans_B));
    return ;
}