Codeforces Beta Round #2B(dp+数学)

贡献了一列WA。。

数学很神奇啊

这个题的关键是怎么才能算尾0的个数只能相乘可以想一下所有一位数相乘除0之外，只有2和5相乘才能得到0 当然那些本身带0的多位数里面肯定含有多少尾0 就含有多少对2和5

这样就知道了就是求2和5 的对数最少的一条路 DP就不用说了递推

注意有0的时候的计算特殊处理一下

 #include <iostream>

 #include<cstdio>

 #include<cstring>

 #include<algorithm>

 #include<stdlib.h>

 #include<vector>

 using namespace std;

 #define N 1010

 #define INF 1e10

 #define LL __int64

 LL dp[N][N][];

 int a[N][N],b[N][N];

 int n;

 char pa[N<<];

 int init(int x,int k)

 {

     int num=;

     while(x)

     {

         if(x%k==)

         {

             num++;

             x/=k;

         }

         else break;

     }

     return num;

 }

 int main()

 {

     int i,j,y,o1,o2,f=;

     scanf("%d",&n);

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

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

         {

             scanf("%d",&y);

             if(y==)

             {

                 o1 = i;

                 o2 = j;

                 f = ;

             }

             int o = init(y,);

             a[i][j] = o;

             o = init(y,);

             b[i][j] = o;

         }

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

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

         {

             dp[i][j][] = INF;

             dp[i][j][] = INF;

         }

     dp[][][] = a[][];

     dp[][][] = b[][];

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

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

         {

             dp[i][j][] = min(dp[i][j][],min(dp[i-][j][],dp[i][j-][])+a[i][j]);

             dp[i][j][] = min(dp[i][j][],min(dp[i-][j][],dp[i][j-][])+b[i][j]);

         }

     int g = ;

     if(f&&min(dp[n][n][],dp[n][n][])>)

     {

         printf("1\n");

         for(i = ; i < o2 ; i++)

         printf("R");

         for(i = ; i < o1 ; i++)

         printf("D");

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

         printf("R");

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

         printf("D");

         return ;

     }

     if(dp[n][n][]<dp[n][n][])

     {

         int i = n,j = n;

         while()

         {

             if(i>&&dp[i][j][]==dp[i-][j][]+a[i][j])

             {

                 i = i-;

                 pa[++g] = 'D';

             }

             else if(j>)

             {

                 j = j-;

                 pa[++g] = 'R';

             }

             if(i==&&j==)

             break;

         }

     }

     else

     {

         int i = n,j = n;

         while()

         {

             if(i>&&dp[i][j][]==dp[i-][j][]+b[i][j])

             {

                 i = i-;

                 pa[++g] = 'D';

             }

             else if(j>)

             {

                 j = j-;

                 pa[++g] = 'R';

             }

             if(i==&&j==)

             break;

         }

     }

     printf("%I64d\n",min(dp[n][n][],dp[n][n][]));

     for(i = g ; i >=  ; i--)

     printf("%c",pa[i]);

     puts("");

     return ;

 }

巴特西

Codeforces Beta Round #2B(dp+数学)

最新文章

热门文章