矩阵(c++,dp)

给出一个n*n的数字矩阵，现在要从(1,1)点走到(n,n)点，每一步只能朝下或者朝右走，在走的过程中要将经过格子的数字累乘起来，并使得这个累乘数值末尾0的数量尽可能的少。编程计算乘积末尾0个数的最小值。

第一行为正整数t(≤5)，表示数据组数；每组数据中，第一行为正整数n(≤500)，接下来是n*n的数字矩阵，每个元素aij不超过109。

对于每组数据，输出乘积末尾0个数的最小值。

输入：

2

3

1 2 3

4 5 6

7 8 9

5

1 2 3 4 5

2 3 4 5 6

3 4 5 6 7

4 5 6 7 8

5 6 7 8 10

输出：

0

2

d代码中给出注释

#include 
#include 
const int N=505;
int g[N][N];
int dp[N][N][2];
int two[N][N], five[N][N];
inline int mn(int a, int b)
{
	return a>b ? b : a;
}
inline void in(int &x)
{
	char c=getchar();
	while (c<'0' || c>'9') c=getchar();
	for (x=0; c>='0' && c<='9'; c=getchar())
		x=x*10+c-'0';
}
int getp(int n, int p) //从n中找出p因子的重数
{
	if (n==0) return 1;
	int s=0;
	while (n%p==0) s++, n/=p;
	return s;
}

int dfs(int x, int y, int z) //记忆化搜索dp
{
	if (dp[x][y][z]>=0)
		return dp[x][y][z];
	int up=1<<30, left=1<<30;
	if (x>1) up=dfs(x-1, y, z);
	if (y>1) left=dfs(x, y-1, z);
	if (z==0)
		dp[x][y][z]=mn(up, left)+two[x][y];
	else
		dp[x][y][z]=mn(up, left)+five[x][y];
	return dp[x][y][z];
}
 
int main(){  
    freopen("ju.in","r",stdin);
    freopen("ju.out","w",stdout);
	int t;
	scanf("%d", &t);
	while (t--)
	{
		memset(dp, -1, sizeof(dp));
		int n;
		bool zero=0;
		scanf("%d", &n);
		for (int i=1; i<=n; i++)
			for (int j=1; j<=n; j++)
			{
				in(g[i][j]); //scanf("%d", &g[i][j]);
				two[i][j]=getp(g[i][j], 2);//g[i][j]中2因子的个数 
				five[i][j]=getp(g[i][j], 5);//g[i][j]中5因子的个数
			}
		dp[1][1][0]=two[1][1];
		dp[1][1][1]=five[1][1];
		dfs(n, n, 0);
		dfs(n, n, 1);
		printf("%dn", mn(dp[n][n][0], dp[n][n][1]));
	}
	return 0;
}