Нужно разобраться с программой по динамическому программированиию про кузнечика и монеты

@VekYchis · Регистрация: 15.10.2019

Студворк — интернет-сервис помощи студентам

Помогите пожалуйста разобраться.

Задание:
Ограничение по времени, сек 2
Ограничение по памяти, мегабайт 64

Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 1 до N . В начале Кузнечик сидит на столбике с номером 1. Он может прыгнуть вперед на расстояние от 1 до K столбиков, считая от текущего.

На каждом столбике Кузнечик может получить или потерять несколько золотых монет (для каждого столбика это число известно). Определите, как нужно прыгать Кузнечику, чтобы собрать наибольшее количество золотых монет. Учитывайте, что Кузнечик не может прыгать назад.

Входные данные
В первой строке вводятся два натуральных числа: N и K ( 2 ≤ N , K ≤ 10000 ), разделённые пробелом. Во второй строке записаны через пробел N - 2 целых числа – количество монет, которое Кузнечик получает на каждом столбике, от 2-го до N - 1 -го. Если это число отрицательное, Кузнечик теряет монеты. Гарантируется, что все числа по модулю не превосходят 10000.

Выходные данные
В первой строке программа должна вывести наибольшее количество монет, которое может собрать Кузнечик. Во второй строке выводится число прыжков Кузнечика, а в третьей строке – номера всех столбиков, которые посетил Кузнечик (через пробел в порядке возрастания).

Программа:

Python
1
2
3
4
5
6
7
8
9
10
n, k = map(int, input().split())
a = list(map(int, input().split()))
b = [0] * (len(a) - 1)
 
for i in range(1, len(a)):
b[i-1] = a[i] * (a[i] > 0 or a[i] == max(a[i: i+k]))
 
print(sum(b))
print(len(filter(lambda x: x != 0, b)))
print(*[n for n, v in enumerate(b, 1) if v != 0])

программа не работает, не понимаю почему. помогите пожалуйста.
и еще, не понимаю как сделать так, чтоб программа соответствовала ограничениям в 2 сек, и 64Мб

@eaa · 18.12.2019, 09:22

задача на динамическое программирование

@VekYchis · 18.12.2019, 10:04 **[ТС]**

именно, только эта информация не привела меня к ее решению. после длительного нахождения в больнице нужно срочно сдать образовавшиеся хвосты. с остальными работами вроде все ок, а вот эту выполнить не могу. завтра уже нужно сдавать (

@eaa · 18.12.2019, 10:16

Можно с этого начать:

Code
1
2
3
4
5
6
dp = [0]*n
dp[0] = 0
dp[1] = a[0]
dp[2] = a[1] + max из предыдущих k элементов dp
...
dp[n] - будет ответ.

@dondublon · 18.12.2019, 11:16

VekYchis,

именно, только эта информация не привела меня к ее решению.

Это, конечно, ещё не говорит о том, что вы дурак. Но всё-таки - вы хоть что-нибудь почитали по ДП?

Понимаете, это задачи нетривиальные, над ними думать надо. Так что "сделайте за меня" на форуме не прокатит. Простые вопросы - да, ДП - нет.

@VekYchis · 18.12.2019, 16:13 **[ТС]**

естественно и даже прекрасный ролик https://www.youtube.com/watch?v=iKj-xI4enLw с разбором этой задачи был просмотрен, только с питоном все настолько туго, что не представляю себе как написать эту программу. поэтому и прошу о помощи. из ролика выходит, что вся программа умещается в 1,5-2 десятка строк, только вот найти варианты ее решения на питоне не удается, а за три дня изучить язык на должном уровне невозможно, увы.

@dondublon · 18.12.2019, 16:24

VekYchis, ну супер. Тогда напишите рекуррентную формулу (словами или простой математикой) и как именно "не работает" ваша программа.

@VekYchis · 18.12.2019, 16:27 **[ТС]**

пока удалось сделать так:

Python
1
2
3
4
5
6
7
8
9
10
11
12
d[1]=0; a[1]=0; a[n]=0;
for (int i=2;i<=n;++i){
int num_max = i - 1;
//поиск предыдущего столбика с максимальным количеством монет
for(int j=max(1,i-k);j<=i-1;++j)
if (d[j]>d[num_max]) {
num_max=j;
}
d[i]=d[num_max]+a[i]; //Текущее максимальное значение
p[i] = num_max;
}
printf("%d\n", d[n]);

компилятор ругается на i в первом цикле. что не так?

@dondublon · 18.12.2019, 16:40

У вас поиск максимума на каждой итерации? Это неправильно. Максимум должен уже быть в предыдущей ячейке массива или в небольшой фиксированном количестве ячеек (две, к примеру).
Именно для этого вы заполняете массив с начала и до конца.
Пригодится описание, что в массивах d и a.
Ну и, конечно, "ругается на" - это несколько неинформативно.

Добавлено через 2 минуты
VekYchis, а, прочитал внимательнее. У вас будет поиск по k ячейкам.
То есть, для заполнения i-й ячейки массива будет поиск по (i-k, i-1). (Возможно, с поправкой на единичку, тут сами посмотрите).

Добавлено через 43 секунды
В целом вы на верном пути.

@VekYchis · 18.12.2019, 18:43 **[ТС]**

так это будет выглядеть на с++. есть ли какие-то программы, позволяющие переконвертировать это в питон?

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
using namespace std;
vector<tuple<uint64_t, bool,int>> num(1000000);
vector<int> coins,steps;
int v, n;
 
int kyznechik(int l) {
    if (l <= 1)        return 0;
    if (get<1>(num[l]) == 0) 
{       int maxcoin = -999999999;int maxV;
            for (int i = 1; i < v+ 1; i++) {
                int g = kyznechik(l - i),b = maxcoin;
                maxcoin = max(maxcoin, g);
                if (b != maxcoin)
                    maxV = l - i; }
            get<0>(num[l]) = maxcoin + coins[l]; get<1>(num[l]) = 1; get<2>(num[l]) = maxV;
            return maxcoin + coins[l]; 
    }
    else {        return get<0>(num[l]);    }
}
 
 
int main()
{ 
    cin >> n >> v;
    coins.resize(n + 1);
    coins[0] = 0; coins[coins.size() - 1] = 0;
    for (int i = 2; i < n; i++) {
        cin >> coins[i];
}
 
    if(n!=3)
{
        cout << kyznechik(n)<<endl;
        int N = n;
        while (N != 1) 
{
            steps.push_back(get<2>(num[N]));
            N = get<2>(num[N]);
}
        cout << steps.size() << endl;
        for (int i = steps.size() - 1; i > -1; i--) {
            cout << steps[i] << " ";}
        cout << n;
    }
    else {
        if (coins[2] > 0) {
            cout << coins[2] << endl;
            cout << 2 << endl;
            cout << "1 2 3";
        }
        else {
            cout << 0 << endl;
            cout << 1 << endl;
            cout << "1 3";
        }
    }
}

@dondublon · 19.12.2019, 11:12

VekYchis, ¯\_(ツ)_/¯

Добавлено через 8 минут
VekYchis, переконвертировать, конечно, можно, хотя бы "в лоб", но это не спортивно. Подумайте, какой катарсис будет, когда вы самостоятельно поймёте идею.

@dondublon · 20.12.2019, 12:35

Идея алгоритма:

Пусть collected - наш массив ВОЗМОЖНЫХ МАКСИМУМОВ собранных монет. От 0 до N, т. е. N+1 штука, на i-й позиции - возможный максимум на i-м столбике. В нулевой позиции - 0. Остальные будем заполнять. Нас интересует последнее значение.
Массив price - сколько монет на i-м столбике.
Тогда:
collected[i+1] = max(по collected от i-k до i-1)+price[i+1].
(При этом надо учесть, что i-k может быть <0, поправочку сами сделаете.)
И, вооружившись этой формулой, заполняем collected от 1 до конца.

Новые блоги и статьи Все статьи Все блоги /
Настройки VS Code Loafer 13.04.2026 { "cmake. configureOnOpen": false, "diffEditor. ignoreTrimWhitespace": true, "editor. guides. bracketPairs": "active", "extensions. ignoreRecommendations": true, . . .	Оптимизация кода на разграничение прав доступа к элементам формы Maks 13.04.2026 Алгоритм из решения ниже реализован на нетиповом документе, разработанного в конфигурации КА2. Задачи, как таковой, поставлено не было, проделанное ниже исключительно моя инициатива. Было так:. . .	Контроль заполнения и очистка дат в зависимости от значения перечислений Maks 12.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: реализовать контроль корректности заполнения дат назначения. . .	Архитектура слоя интернета для сервера-слоя. Hrethgir 11.04.2026 В продолжение https:/ / www. cyberforum. ru/ blogs/ 223907/ 10860. html Знаешь что я подумал? Раз мы все источники пишем в голове ветки, то ничего не мешает добавить в голову такой источник, который сам. . .
Подстановка значения реквизита справочника в табличную часть документа Maks 10.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа "ПланированиеПерсонала", разработанного в конфигурации КА2. Задача: при выборе сотрудника (справочник Сотрудники) в ТЧ документа. . .	Очистка реквизитов документа при копировании Maks 09.04.2026 Алгоритм из решения ниже применим как для типовых, так и для нетиповых документов на самых различных конфигурациях. Задача: при копировании документа очищать определенные реквизиты и табличную. . .	модель ЗдравоСохранения 8. Подготовка к разному выполнению заданий anaschu 08.04.2026 https:/ / github. com/ shumilovas/ med2. git main ветка * содержимое блока дэлэй из старой модели теперь внутри зайца новой модели 8ATzM_2aurI	Блокировка документа от изменений, если он открыт у другого пользователя Maks 08.04.2026 Алгоритм из решения ниже реализован на примере нетипового документа, разработанного в конфигурации КА2. Задача: запретить редактирование документа, если он открыт у другого пользователя. / / . . .

@eaa Status 418 4584 / 2350 / 601 Регистрация: 26.11.2017 Сообщений: 5,262 Записей в блоге: 3
	18.12.2019, 09:22
	задача на динамическое программирование 0

@VekYchis 0 / 0 / 0 Регистрация: 15.10.2019 Сообщений: 18
	18.12.2019, 10:04 [ТС]
	именно, только эта информация не привела меня к ее решению. после длительного нахождения в больнице нужно срочно сдать образовавшиеся хвосты. с остальными работами вроде все ок, а вот эту выполнить не могу. завтра уже нужно сдавать ( 0

@VekYchis 0 / 0 / 0 Регистрация: 15.10.2019 Сообщений: 18
	18.12.2019, 16:13 [ТС]
	естественно и даже прекрасный ролик https://www.youtube.com/watch?v=iKj-xI4enLw с разбором этой задачи был просмотрен, только с питоном все настолько туго, что не представляю себе как написать эту программу. поэтому и прошу о помощи. из ролика выходит, что вся программа умещается в 1,5-2 десятка строк, только вот найти варианты ее решения на питоне не удается, а за три дня изучить язык на должном уровне невозможно, увы. 0

@dondublon 4653 / 2073 / 366 Регистрация: 17.03.2012 Сообщений: 10,183 Записей в блоге: 6
	18.12.2019, 16:24
	VekYchis, ну супер. Тогда напишите рекуррентную формулу (словами или простой математикой) и как именно "не работает" ваша программа. 0

@dondublon 4653 / 2073 / 366 Регистрация: 17.03.2012 Сообщений: 10,183 Записей в блоге: 6
	18.12.2019, 16:40
	У вас поиск максимума на каждой итерации? Это неправильно. Максимум должен уже быть в предыдущей ячейке массива или в небольшой фиксированном количестве ячеек (две, к примеру). Именно для этого вы заполняете массив с начала и до конца. Пригодится описание, что в массивах d и a. Ну и, конечно, "ругается на" - это несколько неинформативно. Добавлено через 2 минуты VekYchis, а, прочитал внимательнее. У вас будет поиск по k ячейкам. То есть, для заполнения i-й ячейки массива будет поиск по (i-k, i-1). (Возможно, с поправкой на единичку, тут сами посмотрите). Добавлено через 43 секунды В целом вы на верном пути. 0

@dondublon 4653 / 2073 / 366 Регистрация: 17.03.2012 Сообщений: 10,183 Записей в блоге: 6
	19.12.2019, 11:12
	VekYchis, ¯\_(ツ)_/¯ Добавлено через 8 минут VekYchis, переконвертировать, конечно, можно, хотя бы "в лоб", но это не спортивно. Подумайте, какой катарсис будет, когда вы самостоятельно поймёте идею. 0

@dondublon 4653 / 2073 / 366 Регистрация: 17.03.2012 Сообщений: 10,183 Записей в блоге: 6
	20.12.2019, 12:35
	Идея алгоритма: Пусть collected - наш массив ВОЗМОЖНЫХ МАКСИМУМОВ собранных монет. От 0 до N, т. е. N+1 штука, на i-й позиции - возможный максимум на i-м столбике. В нулевой позиции - 0. Остальные будем заполнять. Нас интересует последнее значение. Массив price - сколько монет на i-м столбике. Тогда: collected[i+1] = max(по collected от i-k до i-1)+price[i+1]. (При этом надо учесть, что i-k может быть <0, поправочку сами сделаете.) И, вооружившись этой формулой, заполняем collected от 1 до конца. 0