題目：一個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){ ans=tmp; k=i; } } if(ans>1&&zx!=-1){ printf("1\n"); for(int i=1;i<zx;i++) putchar('D'); for(int j=1;j<zy;j++) putchar('R'); for(int i=zx;i<n;i++) putchar('D'); for(int j=zy;j<n;j++) putchar('R'); continue; } string ret=""; int x=n,y=n; while(x!=1||y!=1){ int xx=pre[x][y][k].second.first,yy=pre[x][y][k].second.second; if(xx==x) ret+='R'; else if(yy==y)ret+='D'; k=pre[x][y][k].first;x=xx;y=yy; } reverse(ret.begin(),ret.end()); cout<<ans<<endl<<ret<<endl; } return 0; } #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){ ans=tmp; k=i; } } if(ans>1&&zx!=-1){ printf("1\n"); for(int i=1;i<zx;i++) putchar('D'); for(int j=1;j<zy;j++) putchar('R'); for(int i=zx;i<n;i++) putchar('D'); for(int j=zy;j<n;j++) putchar('R'); continue; } string ret=""; int x=n,y=n; while(x!=1||y!=1){ int xx=pre[x][y][k].second.first,yy=pre[x][y][k].second.second; if(xx==x) ret+='R'; else if(yy==y)ret+='D'; k=pre[x][y][k].first;x=xx;y=yy; } reverse(ret.begin(),ret.end()); cout<<ans<<endl<<ret<<endl; } return 0; }
