Как решить эту проблему с помощью DP?

Question

Ссылка вопроса: http://codeforces.com/contest/2/problem/B

Существует квадратная матрица n × n, состоящая из неотрицательных целых чисел. Вы должны найти на нем такой способ, чтобы

начинается в верхней левой ячейке матрицы; каждая следующая ячейка находится справа или вниз от текущей ячейки; путь заканчивается в нижней правой ячейке. Кроме того, если мы умножим все числа по пути, результат должен быть наименьшим «круглым». Другими словами, он должен заканчиваться наименьшим количеством нулей.

Ввод Первая строка содержит целое число n (2 ≤ n ≤ 1000), n - размер матрицы. Затем следуют n строк, содержащих матричные элементы (неотрицательные целые числа, не превышающие 10^9).

Выход В первой строке напечатайте наименьшее количество конечных нулей. Во второй строке напечатайте соответствующий способ.

Я подумал о следующем: в конце концов, каким бы ни был ответ, он должен содержать минимальные полномочия 2 и 5. Поэтому, что я сделал, для каждой записи во входной матрице я вычислил мощности 2 и 5 и сохранил их в отдельных матрицах.

for (i = 0; i < n; i++) 
    { 
     for (j = 0; j < n; j++) 
     { 
      cin>>foo; 
      matrix[i][j] = foo; 
      int n1 = calctwo(foo); // calculates the number of 2's in factorisation of that number 
      int n2 = calcfive(foo); // calculates number of 5's 
      two[i][j] = n1; 
      five[i][j] = n2; 
     } 
    } 

После этого я сделал это:

for (i = 0; i < n; i++) 
{ 
    for (j = 0; j < n; j++) 
    { 
     dp[i][j] = min(two[i][j],five[i][j]); // Here, dp[i][j] will store minimum number of 2's and 5's. 
    } 
} 

Но выше на самом деле не является действительным ответом, я не знаю, почему? Я применил правильный подход? Или это правильный способ решения этого вопроса?

Редактировать: Вот мои функции вычисления числа двух и пяти чисел в числе.

int calctwo (int foo) 
{ 
    int counter = 0; 
    while (foo%2 == 0) 
    { 
     if (foo%2 == 0) 
     { 
      counter++; 
      foo = foo/2; 
     } 
     else 
      break; 
    } 
    return counter; 
} 

int calcfive (int foo) 
{ 
    int counter = 0; 
    while (foo%5 == 0) 
    { 
     if (foo%5 == 0) 
     { 
      counter++; 
      foo = foo/5; 
     } 
     else 
      break; 
    } 
    return counter; 
} 

Edit2: I/O Пример, как указано в ссылке:

Входной сигнал:

3 
1 2 3 
4 5 6 
7 8 9 

Выход:

0 
DDRR 

Answer 1

Поскольку вы заинтересованы только в количестве завершающих нулей, нужно только рассмотреть полномочия 2, 5, которые вы могли бы держать в двух отдельных nxn массивов. Таким образом, для массива

1 2 3 
4 5 6 
7 8 9 

вы просто держать массивы

the powers of 2 the powers of 5  
0 1 0    0 0 0 
2 0 1    0 1 0 
0 3 0    0 0 0 

Интуиция для задачи состоит в следующем. Обратите внимание: если вы найдете путь, который минимизирует сумму степеней 2 и путь, который минимизирует сумму суммы степеней 5, тогда ответ будет иметь меньшее значение этих двух путей. Таким образом, вы уменьшаете свою проблему до двухкратного применения следующей классической проблемы с dp: найдите путь, начиная с верхнего левого угла и заканчивая в правом нижнем углу, так что сумма его элементов минимальна. Опять же, следуя примеру, мы имеем:

minimal path for the 
powers of 2     value 
* * -       2 
- * * 
- - * 

minimal path for the 
powers of 5     value 
* - -       0 
* - - 
* * * 

так ваш ответ

* - -      
* - - 
* * * 

со значением 0

Примечание 1

Может показаться, что взятие минимума оба оптимальных пути дают только верхнюю границу, поэтому вопрос, который может возникнуть, заключается в следующем: действительно ли эта связь достигнута? Ответ - да.Для удобства пусть число 2 по оптимальному пути 2 равно a, а число 5 по оптимальному пути 5 равно b. Без ограничения общности предположим, что минимум обоих оптимальных путей - это один для мощности 2 (то есть a < b). Пусть число 5 по минимальному пути равно c. Теперь вопрос: есть ли целых 5, так как есть 2 по этому пути (т. Е. c >= a?). Предположим, что ответ отрицательный. Это означает, что на минимальном пути меньше 5, чем на 2 (то есть c < a). Так как оптимальное значение путей 5 - это b, мы имеем, что у каждого 5-го пути есть как минимум b 5 в нем. Это также должно быть верно для минимального пути. Это означает, что c > b. У нас есть то, что c < a так a > b, но исходным предположением было то, что a < b. Противоречие.

Примечание 2

Вы также можете рассмотреть случай, в котором есть элемент 0 в вашей матрице. Я бы предположил, что число конечных нулей, когда произведение равно 1. В этом случае, если алгоритм произвел результат со значением более 1, вы должны вывести 1 и напечатать путь, который проходит через элемент 0.

Answer 2

Вот код. Я использовал pair<int,int> для хранения коэффициента 2 и 5 в матрице.

#include<vector> 
#include<iostream> 
using namespace std; 

#define pii pair<int,int> 
#define F first 
#define S second 
#define MP make_pair 

int calc2(int a){ 
    int c=0; 
    while(a%2==0){ 
     c++; 
     a/=2; 
    } 
    return c; 
} 

int calc5(int a){ 
    int c=0; 
    while(a%5==0){ 
     c++; 
     a/=5; 
    } 
    return c; 
} 

int mini(int a,int b){ 
    return a<b?a:b; 
} 

pii min(pii a, pii b){ 
    if(mini(a.F,a.S) < mini(b.F,b.S)) 
     return a; 
    return b; 
} 

int main(){ 
    int n; 
    cin>>n; 
    vector<vector<pii > > v; 
    vector<vector<int> > path; 

    int i,j; 
    for(i=0;i<n;i++){ 
     vector<pii > x; 
     vector<int> q(n,0); 
     for(j=0;j<n;j++){ 
      int y;cin>>y; 
      x.push_back(MP(calc2(y),calc5(y))); //I store factors of 2,5 in the vector to calculate 
     } 
     x.push_back(MP(100000,100000));  //padding each row to n+1 elements (to handle overflow in code) 
     v.push_back(x); 
     path.push_back(q);  //initialize path matrix to 0 
    } 

    vector<pii > x(n+1,MP(100000,100000)); 
    v.push_back(x);    //pad 1 more row to handle index overflow 

    for(i=n-1;i>=0;i--){ 
     for(j=n-1;j>=0;j--){   //move from destination to source grid 
      if(i==n-1 && j==n-1) 
       continue; 

      //here, the LHS of condition in if block is the condition which determines minimum number of trailing 0's. This is the same condition that is used to manipulate "v" for getting the same result. 
      if(min(MP(v[i][j].F+v[i+1][j].F,v[i][j].S+v[i+1][j].S), MP(v[i][j].F+v[i][j+1].F,v[i][j].S+v[i][j+1].S)) == MP(v[i][j].F+v[i+1][j].F,v[i][j].S+v[i+1][j].S)) 
       path[i][j] = 1;   //go down 
      else 
       path[i][j] = 2;   //go right 
      v[i][j] = min(MP(v[i][j].F+v[i+1][j].F,v[i][j].S+v[i+1][j].S), MP(v[i][j].F+v[i][j+1].F,v[i][j].S+v[i][j+1].S)); 
     } 
    } 

    cout<<mini(v[0][0].F, v[0][0].S)<<endl; //print result 
    for(i=0,j=0;i<=n-1 && j<=n-1;){   //print path (I don't know o/p format) 
     cout<<"("<<i<<","<<j<<") -> "; 
     if(path[i][j]==1) 
      i++; 
     else 
      j++; 
    } 

    return 0; 
} 

Этот код дает прекрасные результаты в отношении проверочных случаев, которые я проверил. Если у вас есть какие-либо сомнения относительно этого кода, спросите в комментариях.

EDIT: Основной мыслительный процесс.
Чтобы добраться до пункта назначения, есть только 2 варианта. Я начал с назначения, чтобы избежать проблемы вычисления пути вперед, потому что если 2 имеют одинаковые минимальные значения, то мы выбрали любой из них. Если путь к пункту назначения уже рассчитан, не имеет значения, что мы делаем.

И минимально - проверить, какая из пар более подходит. Если пара имеет минимум 2 или 5, чем другие, она будет давать меньше 0.

Answer 3

Вот предложение решения с использованием Javascript и функционального программирования. Она опирается на несколько функций:

• функция ядро ​​smallest_trailer рекурсивно проходит через сетку. Я решил пойти в 4 возможных направлениях, оставил «L», правый «R», вниз «D» и «U». В одной и той же ячейке невозможно пройти дважды. Выбранное направление - это число с наименьшим числом конечных нулей. Подсчет конечных нулей посвящен другой функции.
• функция zero_trailer(p,n,nbz) предполагает, что вы прибудете в ячейку со значением p, когда у вас уже есть аккумулятор n и встретил nbz нули на вашем пути. Функция возвращает массив с двумя элементами, новым числом нулей и новым аккумулятором. Аккумулятор будет иметь мощность 2 или 5. Функция использует вспомогательную функцию pow_2_5(n), которая возвращает мощности 2 и 5 внутри n.
• Других функции более анекдотические: deepCopy(arr) делает стандартная глубокая копию массива arr, out_bound(i,j,n) возвращает истину, если ячейка (i,j) находится вне границы сетки размера n, myMinIndex(arr) возвращает мин индекс массива 2 мерных массивов (каждый подмассив содержит nb конечных нулей и путь в виде строки). Минус берется только на первый элемент подмассивов.
• MAX_SAFE_INTEGER - (большая) константа для максимального числа конечных нулей, когда путь неправильный (например, выходит за рамки).

Это код, который будет использоваться на примере, приведенном в комментариях выше и в оригинальной ссылке.

var MAX_SAFE_INTEGER = 9007199254740991; 

function pow_2_5(n) { 
    // returns the power of 2 and 5 inside n 
    function pow_not_2_5(k) { 
    if (k%2===0) { 
     return pow_not_2_5(k/2); 
    } 
    else if (k%5===0) { 
     return pow_not_2_5(k/5); 
    } 
    else { 
     return k; 
    } 
    } 
    return n/pow_not_2_5(n); 
} 

function zero_trailer(p,n,nbz) { 
    // takes an input two numbers p and n that should be multiplied and a given initial number of zeros (nbz = nb of zeros) 
    // n is the accumulator of previous multiplications (a power of 5 or 2) 
    // returns an array [kbz, k] where kbz is the total new number of zeros (nbz + the trailing zeros from the multiplication of p and n) 
    // and k is the new accumulator (typically a power of 5 or 2) 
    function zero_aux(k,kbz) { 
    if (k===0) { 
     return [1,0]; 
    } 
    else if (k%10===0) { 
     return zero_aux(k/10,kbz+1); 
    } 
    else { 
     return [kbz,k]; 
    } 
    } 
    return zero_aux(pow_2_5(p)*n,nbz); 
} 

function out_bound(i,j,n) { 
    return !((i>=0)&&(i<n)&&(j>=0)&&(j<n)); 
} 

function deepCopy(arr){ 
    var toR = new Array(arr.length); 
    for(var i=0;i<arr.length;i++){ 
    var toRi = new Array(arr[i].length); 
    for(var j=0;j<arr[i].length;j++){ 
     toRi[j] = arr[i][j]; 
    } 
    toR[i] = toRi; 
    } 
    return toR; 
} 

function myMinIndex(arr) { 
    var min = arr[0][0]; 
    var minIndex = 0; 
    for (var i = 1; i < arr.length; i++) { 
     if (arr[i][0] < min) { 
      minIndex = i; 
      min = arr[i][0]; 
     } 
    } 
    return minIndex; 
} 

function smallest_trailer(grid) { 
    var n = grid.length; 
    function st_aux(i,j,grid_aux, acc_mult, nb_z, path) { 

    if ((i===n-1)&&(j===n-1)) {   
     var tmp_acc_nbz_f = zero_trailer(grid_aux[i][j],acc_mult,nb_z); 
     return [tmp_acc_nbz_f[0], path]; 
    } 
    else if (out_bound(i,j,n)) { 
     return [MAX_SAFE_INTEGER,[]]; 
    } 
    else if (grid_aux[i][j]<0) { 
     return [MAX_SAFE_INTEGER,[]]; 
    } 
    else { 
     var tmp_acc_nbz = zero_trailer(grid_aux[i][j],acc_mult,nb_z) ; 
     grid_aux[i][j]=-1; 
     var res = [st_aux(i+1,j,deepCopy(grid_aux), tmp_acc_nbz[1], tmp_acc_nbz[0], path+"D"), 
       st_aux(i-1,j,deepCopy(grid_aux), tmp_acc_nbz[1], tmp_acc_nbz[0], path+"U"), 
       st_aux(i,j+1,deepCopy(grid_aux), tmp_acc_nbz[1], tmp_acc_nbz[0], path+"R"), 
       st_aux(i,j-1,deepCopy(grid_aux), tmp_acc_nbz[1], tmp_acc_nbz[0], path+"L")]; 
     return res[myMinIndex(res)];  
    } 
    } 
    return st_aux(0,0,grid, 1, 0, ""); 
} 

myGrid = [[1, 25, 100],[2, 1, 25],[100, 5, 1]]; 
console.log(smallest_trailer(myGrid)); //[0,"RDDR"] 
myGrid = [[1, 2, 100],[25, 1, 5],[100, 25, 1]]; 
console.log(smallest_trailer(myGrid)); //[0,"DRDR"] 
myGrid = [[1, 10, 1, 1, 1],[1, 1, 1, 10, 1],[10, 10, 10, 10, 1],[10, 10, 10, 10, 1],[10, 10, 10, 10, 1]]; 
console.log(smallest_trailer(myGrid)); //[0,"DRRURRDDDD"]