Какое минимальное количество блоков необходимо, чтобы сделать лестницу в N ступенек?

@GCracker · Регистрация: 19.06.2019

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

Всем доброго времени суток! У меня возникла проблема с одной задачкой...

Археологи раскопали Древний Храм, ко входу в который ведет лестница, шириной в 1 (один) метр, из М ступенек различной длины и высоты. Лестница построена из каменных блоков 1x1x1 метр. Археологи хотят для удобства туристов, чтобы лестница состояла из меньшего количества ступенек N. Для этого они могут также устанавливать каменные блоки 1x1x1. Какое минимальное количество блоков необходимо, чтобы сделать лестницу в N ступенек, если известны начальная длина и высота каждой ступеньки. Высоты и длины ступенек новой лестницы могут различаться.
Входные данные
В первой строке через пробел заданы два целых числа M и N (1 ≤ N < M ≤ 100). Далее идут M строк, содержащих пару целых чисел L и H - длина и высота i-ой ступеньки соответственно (1 ≤ L, H ≤ 101). Ступеньки нумеруются снизу вверх.
Выходные данные
В выходной файл выведите единственное число - ответ на задачу.

Прикладываю свой код:

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
#include <algorithm>
#include <cctype>
#include <cmath>
#include <deque>
#include <fstream>
#include <iostream>
#include <iterator>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
 
#define uint unsigned int
#define ll long long
#define ull unsigned long long
 
using namespace std;
 
int main() {
    ull m, n, cur_min, to_delete, ans = 0;
    cin >> m >> n;
    vector<ull> l(m + 1), h(m + 1);
    for (int i = 1; i <= m; ++i) {
        cin >> l[i] >> h[i];
    }
    while (l.size() - 1 > n) {
        cur_min = 2000000000;
        for (int i = 2; i <= l.size() - 1; i++) {
            if (h[i] * l[i - 1] < cur_min) {
                cur_min = h[i] * l[i - 1];
                to_delete = i;
            }
        }
        ans += cur_min;
        l[to_delete - 1] += l[to_delete];
        h[to_delete - 1] += h[to_delete];
        l.erase(l.begin() + to_delete);
        h.erase(h.begin() + to_delete);
    }
    cout << ans << endl;
    return 0;
}

Этот код проходит ровно половину тестов, на остальных выводит Wrong answer. Что не так с алгоритмом?

@covermode · 10.07.2019, 18:39

почему мне так кажется, что здесь добрая часть людей просто едет в сириус и хотят проскочить на халяву

@Max aqq · 12.07.2019, 13:27

не мог бы ты поделиться своим решением?

@Oleg Kopylov · 14.07.2019, 16:00

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

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
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
58
59
60
61
62
63
64
def min(x,y):
    if x<y:
        return x
    else:
        return y
    
 
m,n=[int(x) for x in input().split()]
l,h=[0],[0]
for i in range(1,m+1):
    x,y=[int(f) for f in input().split()]
    l.append(x)
    h.append(y)
g=[-1]*(m+1)
f=g
for i in range(m+1):
    g[i]=[-1]*(m+1)
    f[i]=g[i]
for i in range(1,m+1):
    f[i][i]=0
    g[i][i]=0
 
t=1
adi=1
while adi+1<=m:
    for i in range(1,m):
        s=0
        j=i+adi
        cj=j
        if cj>m:
            break
        s+=g[i][cj-1]
        ci=i
        while g[ci+1][j]>0:
            s+=l[ci+1]*h[j]
            ci+=1
        ci+=1
        g[i][j]=s+l[i]*h[j]
        
    adi+=1
 
 
 
 
    
 
for i in range(2,m+1):
    f[1][i]=g[1][i]
 
k=1
while k<n:
    
    for i in range(k+1,m+1):
        minim=10**20
        for j in range(k,i):
            if f[k][j]>=0:
                t=g[j+1][i]+f[k][j]
                
            if t<minim:
                minim=t
        f[k+1][i]=minim
    k+=1
 
print(f[n][m])

@Max aqq · 14.07.2019, 19:26

благодарю.

Добавлено через 1 минуту
Oleg Kopylov, а вы случаем не решили задачу 4 Опасные ступеньки: количество способов. Если да, то поделитесь решением, пожалуйста)

@nikolayfedoroff · 15.07.2019, 15:51

covermode, на халяву не проскочишь, впереди очный тур

Новые блоги и статьи Все статьи Все блоги /
Транслитерация текста с кириллицы на латиницу (вариант №4) Maks 15.11.2026 Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент". В данной функции нет апострофов,. . .	BitTorrent (версия 4.3.9) и Меню Настройки russiannick 15.11.2026 В меню Настройки можно отключить автоматическое обновление программы. Карта этого меню приложена ниже. Нужный пункт выделен красным. Сервис Настройки Поведение	Транслитерация текста с кириллицы на латиницу (вариант №3) Maks 15.11.2026 Обновленная версия предыдущей обработки. Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён". Изменено отображение буквы Й. Добавлена. . .	Транслитерация текста с кириллицы на латиницу (вариант №2) Maks 13.11.2026 Обновленная версия ранее созданной обработки. Добавлено: - Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
Часы с термометром и праздничным календарем yariko 12.11.2026 Сегодня мы рассмотрим как можно сделать отличные многофункциональные часы. Итак, поставим конкретную задачу: разработать часы с календарем, двумя термодатчиками, выводом поздравительных сообщений. . .	Транслитерация текста с кириллицы на латиницу (вариант №1) Maks 11.11.2026 Решил облегчить жизнь себе и коллегам админам при создании электронных почтовых ящиков для пользователей, в результате написал обработку "Транслитерация текста" с кириллицы на латиницу, а в ней. . .	Книги по геймдизайну, левел-дизайну, игровым механикам и проектированию игрового опыта 8Observer8 08.11.2026 Содержание блога \| English Version 1. 2003 - 06 - Designing Virtual Worlds (1st Edition) Автор: Richard A. Bartle \| Объем: 768 стр. Ссылки: Amazon . . .	Как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Ответ от Джемени ИИ. zorxor 08.11.2026 Джемени, как только я захожу к себе в свою комнату я сразу же с себя снимаю свои трусы. Многие люди, возвращаясь домой, сразу переодеваются в максимально свободную одежду или вовсе предпочитают. . .

@covermode 2 / 1 / 1 Регистрация: 26.06.2019 Сообщений: 5
	10.07.2019, 18:39
	почему мне так кажется, что здесь добрая часть людей просто едет в сириус и хотят проскочить на халяву 0

@Max aqq 0 / 0 / 0 Регистрация: 27.04.2019 Сообщений: 38
	12.07.2019, 13:27
	не мог бы ты поделиться своим решением? 0

@Max aqq 0 / 0 / 0 Регистрация: 27.04.2019 Сообщений: 38
	14.07.2019, 19:26
	благодарю. Добавлено через 1 минуту Oleg Kopylov, а вы случаем не решили задачу 4 Опасные ступеньки: количество способов. Если да, то поделитесь решением, пожалуйста) 0

@nikolayfedoroff 1 / 1 / 0 Регистрация: 29.05.2019 Сообщений: 15
	15.07.2019, 15:51
	covermode, на халяву не проскочишь, впереди очный тур 0