codefroces 2B The least round way

제목: 한 행렬에 숫자가 가득 쓰여 있는데 왼쪽에서 왼쪽으로 내려간다. 매번 아래와 오른쪽으로만 갈 수 있고 한 점을 지나갈 때마다 그 점의 수를 곱한다.경로를 구하는 것이 최종 결과의 끝에 있는 0이 가장 적다.
방법: 일반 경로 DP.DP에서 두 개의 경로를 구하면 하나는 2가 가장 적고 하나는 5가 가장 적으며 그 중에서 가장 작은 값을 비교합니다.애석하게도 처음에는 불필요한 최적화를 썼는데, 시간이 길어지면 틀리기 쉬우니, 이후에는 이런 불필요한 일은 하지 마라

#include <cstdio>
#include<cstring>
#define LMT 1000004
//0°¡Áã°¡
int two[LMT],five[LMT],dd[2][LMT],dp2[LMT],dp5[LMT],sign;
char stack[LMT];
void work(int x,int xi)
{
    if(!x)
    {
        sign=xi+1;
        two[xi]+=10;
        five[xi]+=10;
        return;
    }
    while(x%5==0)
    {
        five[xi]++;
        x/=5;
    }
    while(x%2==0)
    {
        two[xi]++;
        x/=2;
    }
}
int main(void)
{
    int x,n,i,j,ans;
    scanf("%d",&n);
    for(i=0;i<n;i++)
      for(j=0;j<n;j++)
      {
          scanf("%d",&x);
          work(x,i*n+j);
      }
      memset(dp2,-1,sizeof(dp2));
      memset(dp5,-1,sizeof(dp5));
      dp2[0]=two[0];
      dp5[0]=five[0];
      for(x=1;x<n*n;x++)
      {
          i=x/n;
          j=x%n;
          if(i&&(dp2[x]>dp2[(i-1)*n+j]+two[x]||dp2[x]==-1))
          {
              dd[1][x]=1;
              dp2[x]=dp2[(i-1)*n+j]+two[x];
          }
          if(j&&(dp2[x]>dp2[i*n+j-1]+two[x]||dp2[x]==-1))
          {
             dp2[x]=dp2[i*n+j-1]+two[x];
             dd[1][x]=0;
          }
          if(i&&(dp5[x]>dp5[(i-1)*n+j]+five[x]||dp5[x]==-1))
          {
              dd[0][x]=1;
              dp5[x]=dp5[(i-1)*n+j]+five[x];
          }
          if(j&&(dp5[x]>dp5[i*n+j-1]+five[x]||dp5[x]==-1))
          {
            dp5[x]=dp5[i*n+j-1]+five[x];
            dd[0][x]=0;
          }
      }
      int tag,top=0;
      x=n*n-1;
      if(dp2[x]>dp5[x])
      {
          tag=0;
          ans=dp5[x];
      }
      else
      {
          tag=1;
          ans=dp2[x];
      }
      if(ans>1&&sign)
      {
          ans=1;
          sign--;
          i=sign/n;j=sign%n;
          int ii=n-1,jj=n-1;
          while(jj!=j)
          {
              stack[top++]='R';
              jj--;
          }
          while(ii)
          {
              stack[top++]='D';
              ii--;
          }
          while(jj)
          {
              stack[top++]='R';
              jj--;
          }
      }
      else
      {
           while(x)
         {
             i=x/n;
             j=x%n;
             if(dd[tag][x])
            {
              x=(i-1)*n+j;
              stack[top++]='D';
            }
             else
            {
              x=i*n+j-1;
              stack[top++]='R';
            }
          }
      }
      printf("%d
",ans);
      while(top>0)printf("%c",stack[--top]);
        printf("
");
      return 0;
}