程式師世界 >> 編程語言 >> C語言 >> C++ >> C++入門知識 >> Codeforces #2B The least round way(DP)

Codeforces #2B The least round way(DP)

編輯：C++入門知識

Codeforces #2B The least round way(DP)

Description

有一個n*n的正整數矩陣，要你求一條從第一行第一列的格子到第n行第n列的路，使得你走過的格子裡面的數乘起來的值末尾的零的個數最小。輸出最小個數。

Input

第一行包含1個數n。
接下來n行每行n個數字。

Output

一個數字表示末尾零最小個數。

Sample Input

Sample Output

由於都是正數，對這個來說只需統計最少的2或5即可。相對簡單。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )
typedef long long LL;
typedef pairpil;
const int INF=0x3f3f3f3f;
const int maxn=1010;
int dp[maxn][maxn][2];
int path[maxn][maxn][2];
int mp[maxn][maxn][2];
int n;
void print(int i,int j)
{
    if(i==1&&j==1)
        return ;
    print(path[i][j][0],path[i][j][1]);
    if(i-path[i][j][0]==1&&j==path[i][j][1]) printf("%c",'D');
    else printf("%c",'R');
}
int main()
{
    int x,cnt1,cnt2,temp;
    while(~scanf("%d",&n))
    {
        REPF(i,1,n)
        {
            REPF(j,1,n)
            {
                scanf("%d",&x);
                cnt1=cnt2=0;temp=x;
                while(temp%2==0)
                {
                    temp/=2;
                    cnt1++;
                }
                while(x%5==0)
                {
                    x/=5;
                    cnt2++;
                }
                mp[i][j][0]=cnt1;
                mp[i][j][1]=cnt2;
            }
        }
        CLEAR(dp,INF);
        dp[1][1][0]=mp[1][1][0];
        dp[1][1][1]=mp[1][1][1];
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                for(int k=0;k<2;k++)//0:2 1:5
                {
                    if(i>1&&dp[i][j][k]>dp[i-1][j][k]+mp[i][j][k])
                    {
                        dp[i][j][k]=dp[i-1][j][k]+mp[i][j][k];
                        path[i][j][0]=i-1;path[i][j][1]=j;
                    }
                    if(j>1&&dp[i][j][k]>dp[i][j-1][k]+mp[i][j][k])
                    {
                        dp[i][j][k]=dp[i][j-1][k]+mp[i][j][k];
                        path[i][j][0]=i;path[i][j][1]=j-1;
                    }
                }
            }
        }
        printf("%d\n",min(dp[n][n][0],dp[n][n][1]));
//        print(n,n);
//        puts("");
    }
    return 0;
}
/*

再看Codeforces 2B:

Description

There is a square matrix n?×?n, consisting of non-negative integer numbers. You should find such a way on it that

starts in the upper left cell of the matrix;each following cell is to the right or down from the current cell;the way ends in the bottom right cell.

Moreover, if we multiply together all the numbers along the way, the result should be the least "round". In other words, it should end in the least possible number of zeros.

Input

The first line contains an integer number n (2?≤?n?≤?1000), n is the size of the matrix. Then follow n lines containing the matrix elements (non-negative integer numbers not exceeding10⁹).

Output

In the first line print the least number of trailing zeros. In the second line print the correspondent way itself.

Sample Input

Input

Output

0
DDRR

Source

不僅要輸出路徑，而且矩陣中還帶了0，這就是麻煩的地方；

題解：對於要輸出的路徑，記錄前面的一個狀態即可，對於0的處理，如果到終點的2或

5的個數大於等於1了，而矩陣中含0，這時候就是直接答案就是1個0，路徑只需找到任意

一個0所在的行列輸出即可。

#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
#include
using namespace std;
#define REPF( i , a , b ) for ( int i = a ; i <= b ; ++ i )
#define REP( i , n ) for ( int i = 0 ; i < n ; ++ i )
#define CLEAR( a , x ) memset ( a , x , sizeof a )
typedef long long LL;
typedef pairpil;
const int INF=0x3f3f3f3f;
const int maxn=1010;
int dp[maxn][maxn][2];
int path1[maxn][maxn][2];
int path2[maxn][maxn][2];
int mp[maxn][maxn][2];
int n;
void print1(int i,int j)
{
    if(i==1&&j==1)
        return ;
    print1(path1[i][j][0],path1[i][j][1]);
    if(i-path1[i][j][0]==1&&j==path1[i][j][1]) printf("%c",'D');
    else printf("%c",'R');
}
void print2(int i,int j)
{
    if(i==1&&j==1)
        return ;
    print2(path2[i][j][0],path2[i][j][1]);
    if(i-path2[i][j][0]==1&&j==path2[i][j][1]) printf("%c",'D');
    else printf("%c",'R');
}
int main()
{
    int x,cnt1,cnt2,temp,ans;
    int sx,sy;
    while(~scanf("%d",&n))
    {
        int flag=1;
        CLEAR(mp,0);
        REPF(i,1,n)
        {
            REPF(j,1,n)
            {
                scanf("%d",&x);
                cnt1=cnt2=0;temp=x;
                if(x==0)
                {
                    mp[i][j][0]=mp[i][j][1]=1;
                    sx=i;sy=j;flag=0;continue;
                }
                while(temp%2==0)
                {
                    temp/=2;
                    cnt1++;
                }
                while(x%5==0)
                {
                    x/=5;
                    cnt2++;
                }
                mp[i][j][0]=cnt1;
                mp[i][j][1]=cnt2;
            }
        }
        CLEAR(dp,INF);
        dp[1][1][0]=mp[1][1][0];
        dp[1][1][1]=mp[1][1][1];
        for(int i=1;i<=n;i++)
        {
            for(int j=1;j<=n;j++)
            {
                for(int k=0;k<2;k++)//0:2 1:5
                {
                    if(i>1&&dp[i][j][k]>dp[i-1][j][k]+mp[i][j][k])
                    {
                        dp[i][j][k]=dp[i-1][j][k]+mp[i][j][k];
                        if(!k)
                        {
                            path1[i][j][0]=i-1;
                            path1[i][j][1]=j;
                        }
                        else
                        {
                            path2[i][j][0]=i-1;
                            path2[i][j][1]=j;
                        }
                    }
                    if(j>1&&dp[i][j][k]>dp[i][j-1][k]+mp[i][j][k])
                    {
                        dp[i][j][k]=dp[i][j-1][k]+mp[i][j][k];
                        if(!k)
                        {
                            path1[i][j][0]=i;
                            path1[i][j][1]=j-1;
                        }
                        else
                        {
                            path2[i][j][0]=i;
                            path2[i][j][1]=j-1;
                        }
                    }
                }
            }
        }
        ans=min(dp[n][n][0],dp[n][n][1]);
        if(ans>=1&&!flag)
        {
            printf("%d\n",1);
            for(int i=0;i