2015年4月20日 星期一

2015/04/20 Codeforces 2B. The least round way

/*
    考慮讓2的數量盡量少
    和讓5的數量盡量少 兩種走法

    是說 要處理0的case
    超機車的 =口="
*/
// http://codeforces.com/contest/2/problem/B
#include <iostream>
#include <cstdio>
#include <queue>

using namespace std;

typedef pair<int, int> pr;
#define x first
#define y second

#define INF 1e9
pr DP[2000][2000];
int num[2000][2000];
int F[2000][2000];

int N;
deque<char> deq;

pr cal(int x)
{
    if( x == 0 ) return pr(INF, -INF);

    int a = 0, b = 0;
    while( x%5 == 0 ) a++, x/=5;
    while( x%2 == 0 ) b++, x/=2;
    return pr(a, b);
}

int Ans;

void process()
{
    if( min(DP[N][N].x, DP[N][N].y) < Ans )
    {
        Ans = min(DP[N][N].x, DP[N][N].y);

        int nx = N, ny = N;
        deq.clear();

        while(1)
        {
            if( nx == 1 && ny == 1 ) break;

            if( F[nx][ny] ) nx--, deq.push_front('D');
            else ny--, deq.push_front('R');
        }
    }
}

int main()
{
    scanf("%d", &N);

    for(int Ni = 1; Ni <= N; Ni++)
        for(int Nj = 1; Nj <= N; Nj++)
            scanf("%d", &num[Ni][Nj]);

    Ans = INF;

    fill(DP[0], DP[2000-1]+2000, pr(INF, INF));
    DP[1][0] = pr(INF-1, INF-1);

    for(int Ni = 1; Ni <= N; Ni++)
        for(int Nj = 1; Nj <= N; Nj++)
        {
            if( DP[Ni-1][Nj] < DP[Ni][Nj-1] ) DP[Ni][Nj] = DP[Ni-1][Nj], F[Ni][Nj] = 1;
            else DP[Ni][Nj] = DP[Ni][Nj-1], F[Ni][Nj] = 0;

            if( num[Ni][Nj] == 0 ) DP[Ni][Nj] = pr(1, 1);
        }

    process();

    fill(DP[0], DP[2000-1]+2000, pr(INF, INF));
    DP[1][0] = pr(0, 0);

    for(int Ni = 1; Ni <= N; Ni++)
        for(int Nj = 1; Nj <= N; Nj++)
        {
            if( num[Ni][Nj] == 0 ) continue;

            if( DP[Ni-1][Nj] < DP[Ni][Nj-1] ) DP[Ni][Nj] = DP[Ni-1][Nj], F[Ni][Nj] = 1;
            else DP[Ni][Nj] = DP[Ni][Nj-1], F[Ni][Nj] = 0;

            pr p = cal(num[Ni][Nj] );
            DP[Ni][Nj].x += p.x; DP[Ni][Nj].y += p.y;
            DP[Ni][Nj] = min(DP[Ni][Nj], pr(INF, INF));
        }

    process();

    fill(DP[0], DP[2000-1]+2000, pr(INF, INF));
    DP[1][0] = pr(0, 0);

    for(int Ni = 1; Ni <= N; Ni++)
        for(int Nj = 1; Nj <= N; Nj++)
        {
            if( num[Ni][Nj] == 0 ) continue;

            if( DP[Ni-1][Nj] < DP[Ni][Nj-1] ) DP[Ni][Nj] = DP[Ni-1][Nj], F[Ni][Nj] = 1;
            else DP[Ni][Nj] = DP[Ni][Nj-1], F[Ni][Nj] = 0;

            pr p = cal(num[Ni][Nj] );
            DP[Ni][Nj].x += p.y; DP[Ni][Nj].y += p.x;
            DP[Ni][Nj] = min(DP[Ni][Nj], pr(INF, INF));
        }

    process();

    if( Ans >= 0 ) printf("%d\n", Ans);
    else puts("1");

    for(int di = 0; di < deq.size(); di++)
        printf("%c", deq[di]);
    puts("");
}

沒有留言:

張貼留言