Codeforces Beta Round铂2 B.The least round way dp

B.The least round way
テーマ接続:
http://www.codeforces.com/contest/2/problem/B
Description
The re is a square matirix n̵×̵n，consisting of n on-negative integer numbers.You shound find such a way on it that
starts in the up left cell of the matirix；each following cell is to the right or down from the current cell；the way ends in the bottom right cell.Moreover，if we multiplly together all the numbers along the way，the reult shound be the least"round"In other words，it shoud end the least possible.
Input
The first line contains an integer number n（2̵≦𔎅n̵≦𔎅1000）、n is the size of the matrix.The n follow n line containing the matremens（non-negative integer nbers noceement 109）
Output
In the first line prest the least number of triling zros.In the second line the coresont the corese pondent way itself.
Sample Input
3 1 2 3 4 5 6 7 8 9
Sample Output
0 DDRR
ベント
題意
n＊nの行列をあげます。
そしてこの行列は左上から右下に行く必要があります。
右か下しか歩けません。
あなたが通過した数を、乗積した後の0の数が一番少ないです。
クイズ:
dp[i][j][0]はi，j位置，2の因子の最小数を表します。
dp[i][j][1]はi，j位置，5の因子の最低数を表します。
そして答えは明らかにmin（dp[n][0]，dp[n][n][1]）です。そしてdfsを逆さにして答えを出力すればいいです。
ここには0の位置があると答えが一番多くて1になります。これは明らかです。
そしてなくなりました
コード

#include<bits/stdc++.h>
using namespace std;
const int maxn = 1100;
const int inf = 1e9;
int dp[maxn][maxn][2];
int cnt[maxn][maxn][2];
int g[maxn][maxn][2];
int n,a[maxn][maxn];
void solve(int x,int y,int now)
{
    if(x==1&&y==1)return;
    if(g[x][y][now]==1)solve(x-1,y,now),printf("D");
    else solve(x,y-1,now),printf("R");
}
int main()
{
    scanf("%d",&n);
    for(int i=1;i<=n;i++)
        for(int j=1;j<=n;j++)
            scanf("%d",&a[i][j]);
    int flagx=0,flagy=0;
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(a[i][j]==0)
            {
                flagx=i,flagy=j;
                break;
            }
            int pre = a[i][j];
            while(a[i][j]%2==0)cnt[i][j][0]++,a[i][j]/=2;
            while(a[i][j]%5==0)cnt[i][j][1]++,a[i][j]/=5;
        }
    }
    memset(dp,0x3f,sizeof(dp));
    memset(g,0,sizeof(g));
    dp[1][1][0]=cnt[1][1][0],dp[1][1][1]=cnt[1][1][1];
    for(int i=1;i<=n;i++)
    {
        for(int j=1;j<=n;j++)
        {
            if(i==1&&j==1)continue;
            for(int k=0;k<2;k++)
            {
                dp[i][j][k]=cnt[i][j][k]+min(dp[i-1][j][k],dp[i][j-1][k]);
                if(dp[i-1][j][k]<dp[i][j-1][k])g[i][j][k]=1;
            }
        }
    }
    int ans = min(dp[n][n][0],dp[n][n][1]);
    int st;
    if(dp[n][n][0]<dp[n][n][1])st=0;
    else st=1;
    if(ans==0)puts("0");
    else if(flagx&&flagy)
    {
        puts("1");
        int nowx=1,nowy=1;
        while(nowx<flagx)nowx++,printf("D");
        while(nowy<flagy)nowy++,printf("R");
        while(nowx<n)nowx++,printf("D");
        while(nowy<n)nowy++,printf("R");
        return 0;
    }
    else printf("%d
",ans);
    solve(n,n,st);
}