Консультации

Какая к черту простая динамика?

Какая к черту простая динамика?

от Никита Пушкин -
Number of replies: 10
Ну и что тут простого? Как решить эту задачу?
In reply to Никита Пушкин

Re: Какая к черту простая динамика?

от Peter Cherepanov -
Нужно обходить дерево поиска в ширину и запоминать результаты, чтобы сократить перебор.
In reply to Peter Cherepanov

Re: Какая к черту простая динамика?

от Григорий Резников -
Тут проще заходит.
Можно просто утверждать, что a[i]=min(a[i-1],a[i/2],a[i/3]) и убирать последние два параматра,если i не делится на 2 или на 3.
In reply to Григорий Резников

Re: Какая к черту простая динамика?

от Никита Пушкин -
Я решил просто делить число на 3, если оно делится; в противном случае делю на 2, если оно делится; в противном случае вычитаю 1. Ответ неверный выходит.

А если применять динамическое программирование с массивом и циклом, то массив тупо не поместит в себе 10^6 элементов. Подскажите, как это сделать?

Блин, как вообще все это освоить? Мне это трудно дается.
In reply to Никита Пушкин

Re: Какая к черту простая динамика?

от Антон Карабанов -
"массив тупо не поместит в себе 10^6 элементов"
Отчего же? Памяти аж 64 Мб выделено.
Да и времени 3 секунды - можно пешком дойти :)
In reply to Григорий Резников

Re: Какая к черту простая динамика?

от Владислав Толстиков -
In reply to Владислав Толстиков

где у меня ошибка?

от Кирилл Майченко -
#include <iostream>

using namespace std;

int main()
{
    int a[100000];
    int n,i,k,l;

    cin >> n;
    a[1] = 0; a[2] = 1; a[3] = 1; a[4] = 2; a[5] = 3;
    a[6] = 2; a[7] = 3; a[8] = 3; a[9] = 3;

    for (i = 10; i <= n; i++)
    {
        if ((i % 2 == 0) || (i % 3 == 0))
        {
            a[i] = 1 + min(min(a[i-1],a[i/2]),a[i/3]);
        } else
        {
            a[i] = a[i-1]+1;
        }
    }

    cout << a[n] << endl;
    return 0;
}