Динамика - задача про Кузнечика с монетками. Не проходит по времени три теста

@yankis · Регистрация: 11.04.2018

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

Здравствуйте, требуется помощь.
Кузнечик прыгает по столбикам, расположенным на одной линии на равных расстояниях друг от друга. Столбики имеют порядковые номера от 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
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
n, k = map(int, input().split())
s = list(map(int, input().split()))
b = []
it = []
b.append(0)
a = []
a.append(-1)
for i in range(1, n - 1):
   if i < k :
    b.append(max(b[0:i]) + s[i - 1])
    a.append(b.index(max(b[0 :i])))
   else:
    b.append(max(b[i - k:i]) + s[i - 1])
    a.append(b.index(max(b[i - k:i])))
i += 1
b.append(max(b[i - k:i]))
a.append(b.index(max(b[i - k:i])))
now = n - 1
while now > 0 :
   it.append(a[now])
   now = a[now]
print(b[n - 1])
print(len(it))
for i in range(len(it)):
   print(it[len(it) - i - 1] + 1, end = " ")
print(n)

Не проходит 12 ,16, 21 тесты - более 2 секунд, что улучшить?

@no swear · 18.07.2019, 11:34

Ограничения входных данных большие можно сказать. Если предположить что n = 10'000 и k = 10'000 то всего получается примерно порядка 10^8 операций и тем более вы пишите не на самом подходящем языке на котором следует решать задачи данного типа. Можно попробовать поменять язык и сдать например с Си.

Вот мой код, подробно не тестировал но основные тесты проходит

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
#include <fstream>
 
int main() {
    std::ifstream fin("c:\\input.txt");
    std::ofstream fout("c:\\output.txt");
    int n, max, step;
    fin >> n >> k;
    int *dynamic, *way, *currentWay, *arr, currentWaySize;
    dynamic = new int[n];
    way = new int[n];
    currentWay = new int[n];
    arr = new int[n];
    for (int i = 1; i < n - 1; ++i) {
        fin >> arr[i];
    }
    dynamic[0] = arr[0] = 0;
    arr[n - 1] = 0;
    way[0] = 0;
    for (int i = 1; i < n; ++i) {
        max = INT_MIN;
        for (int j = 1; j <= k && j <= i; ++j) {
            if (max < dynamic[i - j]) {
                max = dynamic[i - j];
                step = j;
            }
        }
        way[i] = step;
        dynamic[i] = arr[i] + max;
    }
    fout << dynamic[n - 1] << std::endl;
    currentWaySize = 0;
    for (int i = n - 1; i > 0; i = way[i]) {
        currentWay[currentWaySize++] = way[i];
    }
    for (int i = currentWaySize - 1; i > -1; --i) {
        if (currentWay[i])
            fout << currentWay[i] << std::ends;
    }
    delete[] dynamic, way, arr, currentWay;
    fin.close();
    fout.close();
}

И ещё хочу сказать что нужно попробовать использовать бинарную кучу чтобы хранить максимальный элемент на промежутке от a[i-k], a[i-k+1]...a[i]. Тогда сложность может сползти с O(n * k) До O(n * log(k)).

Новые блоги и статьи Все статьи Все блоги /
PhpStorm 2025.3: WSL Terminal всегда стартует в ~ and_y87 14.12.2025 PhpStorm 2025. 3: WSL Terminal всегда стартует в ~ (home), игнорируя директорию проекта Симптом: После обновления до PhpStorm 2025. 3 встроенный терминал WSL открывается в домашней директории. . .	Как объединить две одинаковые БД Access с разными данными VikBal 11.12.2025 Помогите пожалуйста !! Как объединить 2 одинаковые БД Access с разными данными.	Новый ноутбук volvo 07.12.2025 Всем привет. По скидке в "черную пятницу" взял себе новый ноутбук Lenovo ThinkBook 16 G7 на Амазоне: Ryzen 5 7533HS 64 Gb DDR5 1Tb NVMe 16" Full HD Display Win11 Pro	Музыка, написанная Искусственным Интеллектом volvo 04.12.2025 Всем привет. Некоторое время назад меня заинтересовало, что уже умеет ИИ в плане написания музыки для песен, и, собственно, исполнения этих самых песен. Стихов у нас много, уже вышли 4 книги, еще 3. . .	От async/await к виртуальным потокам в Python IndentationError 23.11.2025 Армин Ронахер поставил под сомнение async/ await. Создатель Flask заявляет: цветные функции - провал, виртуальные потоки - решение. Не threading-динозавры, а новое поколение лёгких потоков. Откат?. . .
Поиск "дружественных имён" СОМ портов Argus19 22.11.2025 Поиск "дружественных имён" СОМ портов На странице: https:/ / norseev. ru/ 2018/ 01/ 04/ comportlist_windows/ нашёл схожую тему. Там приведён код на С++, который показывает только имена СОМ портов, типа,. . .	Сколько Государство потратило денег на меня, обеспечивая инсулином. Programma_Boinc 20.11.2025 Сколько Государство потратило денег на меня, обеспечивая инсулином. Вот решила сделать интересный приблизительный подсчет, сколько государство потратило на меня денег на покупку инсулинов. . . .	Ломающие изменения в C#.NStar Alpha Etyuhibosecyu 20.11.2025 Уже можно не только тестировать, но и пользоваться C#. NStar - писать оконные приложения, содержащие надписи, кнопки, текстовые поля и даже изображения, например, моя игра "Три в ряд" написана на этом. . .	Мысли в слух kumehtar 18.11.2025 Кстати, совсем недавно имел разговор на тему медитаций с людьми. И обнаружил, что они вообще не понимают что такое медитация и зачем она нужна. Самые базовые вещи. Для них это - когда просто люди. . .	Создание Single Page Application на фреймах krapotkin 16.11.2025 Статья исключительно для начинающих. Подходы оригинальностью не блещут. В век Веб все очень привыкли к дизайну Single-Page-Application . Быстренько разберем подход "на фреймах". Мы делаем одну. . .