CF 2B The least round way(DP)
题目：一个n*n的矩阵，每次只能向下或者向右，从左上到右下，一条路径上的所有数相乘，判断末尾最少几个0
http://codeforces.com/problemset/problem/2/B
在群里看到叉姐推荐的，就做了，你值得拥有！
相乘末尾为0，说明是2*5，最后的乘积可以表示成2^a * 5^b * other ，那么最后0的个数便是min(a,b)
dp[i][j][0]表示记录因子2的个数最少的情况
dp[i][j][1]表示记录因子5的个数最少的情况
但是有一个地方有trick，那就是矩阵中的数可以为0
乘积就为0。
所以先把0当作10跑一次DP，如果结果为0，说明有一条路径不经过0，而且末尾没有0
如果结果大于1，就可以选择经过0的这条路，那么答案便是1
[cpp]
#include<iostream>
#include<cstdio>
#include<map>
#include<cstring>
#include<cmath>
#include<vector>
#include<algorithm>
#include<set>
#include<string>
#include<queue>
#define inf 1000000005
#define M 40
#define N 10005
#define maxn 300005
#define eps 1e-8
#define zero(a) fabs(a)<eps
#define Min(a,b) ((a)<(b)?(a):(b))
#define Max(a,b) ((a)>(b)?(a):(b))
#define pb(a) push_back(a)
#define mp(a,b) make_pair(a,b)
#define mem(a,b) memset(a,b,sizeof(a))
#define LL long long
#define MOD 1000000009
#define lson step<<1
#define rson step<<1|1
#define sqr(a) ((a)*(a))
#define Key_value ch[ch[root][1]][0]
#define test puts("OK");
#define pi acos(-1.0)
#define lowbit(x) ((-(x))&(x))
#define HASH1 1331
#define HASH2 10001
#pragma comment(linker, "/STACK:1024000000,1024000000")
using namespace std;
//dp[i][j][k][l]表示到达(i,j),l=0表示two,l=1表示five
int dp[1005][1005][2][2];
int n,a[1005][1005];
pair<int,pair<int,int> > pre[1005][1005][2];
int way[2][2]={0,1,1,0};
int get(int num,int fac){
int ret=0;
if(!num) return 1;
while(num&&(num%fac)==0){
ret++;
num/=fac;
}
return ret;
}
int main(){
//freopen("input.txt","r",stdin);
while(scanf("%d",&n)!=EOF){
int zx=-1,zy=-1;
for(int i=1;i<=n;i++)
for(int j=1;j<=n;j++){
scanf("%d",&a[i][j]);
if(a[i][j]==0)
zx=i,zy=j;
}
mem(dp,-1);
for(int j=0;j<2;j++)
for(int k=0;k<2;k++)
dp[0][1][j][k]=dp[1][0][j][k]=0;
for(int i=1;i<=n;i++){
for(int j=1;j<=n;j++){
int two=get(a[i][j],2),five=get(a[i][j],5);
for(int r=0;r<2;r++){
int x=i-way[r][0],y=j-way[r][1];
for(int k=0;k<2;k++){
if(dp[x][y][k][0]==-1||dp[x][y][k][1]==-1) continue;
int now_two=dp[x][y][k][0]+two,now_five=dp[x][y][k][1]+five;
if(dp[i][j][k][0]==-1){
dp[i][j][k][0]=now_two;
dp[i][j][k][1]=now_five;
pre[i][j][k]=mp(k,mp(x,y));
}
else if(k&&now_two<dp[i][j][k][0]){
dp[i][j][k][0]=now_two;
dp[i][j][k][1]=now_five;
pre[i][j][k]=mp(k,mp(x,y));
}
else if(!k&&now_five<dp[i][j][k][1]){
dp[i][j][k][0]=now_two;
dp[i][j][k][1]=now_five;
pre[i][j][k]=mp(k,mp(x,y));
}
}
}
}
}
int ans=inf,k;
for(int i=0;i<2;i++){
if(dp[n][n][i][0]==-1) continue;
int tmp=min(dp[n][n][i][0],dp[n][n][i][1]);
if(tmp<ans){ &
补充：软件开发 , C++ ,
