hihocoder 1241：Best Route in a Grid

#1241 : Best Route in a Grid

时间限制:10000ms

单点时限:1000ms

内存限制:256MB

描述

给定一个N行N列的非负整数方阵，从左上角(1,1)出发，只能向下或向右走，且不能到达值为0的方格，求出一条到达右下角的最佳路径。所谓最佳路径是指途经的数的乘积的末尾连续的0最少。

输入

输入文件的第一行包含一个整数N，其中1≤N≤1000。

接下来的N行每行包含N个非负整数，其中每个数小于等于1,000,000。

数据保证至少存在一条不全为0的路径。

输出

输出文件仅一行，包含一个整数，表示要求的最佳路径上所有数字乘积的末尾连续零的个数。

样例输入

样例输出

对每一个数查其因子2和5的个数，然后对每一条路径取其最小值(一开始居然想不通这里。。。)。标记哪里可以走，哪里不能走。一开始就标记(1,1)位置可以走，之后就是由走的情况决定，如果该位置的dp5的值为1000002，说明这里的值是不能走的，往下也对其不处理。

代码：

#include <iostream>

#include <algorithm>

#include <cmath>

#include <vector>

#include <string>

#include <cstring>

#pragma warning(disable:4996)

using namespace std;

int n,flag;

long long ans;

int val[1002][1002];

int dp5[1002][1002];

int dp2[1002][1002];

int a2[1000002];

int a5[1000002];

int dog(int val,int p)

{

	if (val==0) return 0;

	int tot=0;

	while(val%p==0)

	{

		tot++;

		val=val/p;

	}

	return tot;

}

void cal(int i)

{

	int temp=i;

	while((i%2==0||i%5==0)&&i!=0)

	{

		if(i%2==0)

		{

			a2[temp]++;

			i=i/2;

		}

		if(i%5==0)

		{

			a5[temp]++;

			i=i/5;

		}

	}

}

void init()

{

	memset(a2,0,sizeof(a2));

	memset(a5,0,sizeof(a5));

	int i;

	for(i=1;i<=1000000;i++)

	{

		cal(i);

	}

}

int main()

{

	freopen("i.txt","r",stdin);

	freopen("o.txt","w",stdout);

	init();

	int i,j;

	scanf("%d",&n);

	memset(val,0,sizeof(val));

	for(i=1;i<=n;i++)

	{

		for(j=1;j<=n;j++)

		{

			scanf("%d",&val[i][j]);

		}

	}

	for(i=0;i<=n;i++)

	{

		for(j=0;j<=n;j++)

		{

			dp5[i][j]=1000002;

			dp2[i][j]=1000002;

		}

	}

	dp5[0][1]=0;

	dp5[1][0]=0;

	for(i=1;i<=n;i++)

	{

		for(j=1;j<=n;j++)

		{

			if(val[i][j]==0)

				continue;

			if(i==1&&j==1)

			{

				dp5[i][j]=a5[val[i][j]];

				dp2[i][j]=a2[val[i][j]];

				continue;

			}

			if(val[i][j-1]!=0&&dp5[i][j-1]!=1000002)

			{

				dp5[i][j]=dp5[i][j-1]+a5[val[i][j]];

				dp2[i][j]=dp2[i][j-1]+a2[val[i][j]];

			}

			if(val[i-1][j]!=0&&dp5[i-1][j]!=1000002)

			{

				dp5[i][j]=min(dp5[i][j],dp5[i-1][j]+a5[val[i][j]]);

				dp2[i][j]=min(dp2[i][j],dp2[i-1][j]+a2[val[i][j]]);

			}

		}

	}

	cout<<min(dp5[n][n],dp2[n][n])<<endl;

	//system("pause");

	return 0;

}

巴特西

hihocoder 1241：Best Route in a Grid

#1241 : Best Route in a Grid

描述

输入

输出

最新文章

热门文章