Какое минимальное количество блоков необходимо, чтобы сделать лестницу в 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, на халяву не проскочишь, впереди очный тур

Новые блоги и статьи Все статьи Все блоги /
Алиса нашла кучу ошибок компиляции и запуска в проекте, который без проблем компилировался и запускался))) anaschu 30.06.2026 Я пока посмеюся, но завтра проверю. А вообще интерсно. Дал алисе файл, в котором точно нет ошибок компиляции и запуска, и попросил их найти. Нашла кучу))) Критические ошибки, мешающие компиляции и. . .	сукцессия 16. Общий обзор, в основном что бы другие ии поняли anaschu 29.06.2026 # Передаточный документ: модель микоризной сукцессии (для нового чата) Этот документ предназначен для того, чтобы новый чат Claude мог продолжить работу без необходимости заново разбираться в. . .	сукцессия 15 неявная схема anaschu 29.06.2026 Алиса Калибровка параметров симбиотической модели: технический обзор Содержание: Введение Постановка проблемы Технические аспекты реализации Процесс внедрения изменений	сукцессия 14. Обновленная схема модели anaschu 28.06.2026 ГЛОБАЛЬНАЯ ОПИСАТЕЛЬНАЯ СПЕЦИФИКАЦИЯ ЭКОСИСТЕМНОЙ МОДЕЛИ «SOIL CHEMISTRY & MYCORRHIZA 2. 0» https:/ / ibb. co/ NnkGpfMd Представленная интегрированная схема описывает непрерывную нелинейную. . .
сукцессия 13. Питон модель трехзонного мицелия, пока что в основном арбускулярного anaschu 28.06.2026 ## Разработка агентной модели микоризной сукцессии: от выявления артефактов к созданию комплексной системы ### Аннотация Представлено исследование по разработке агентной модели микоризной. . .	сукцессия 12. краткий список проверок модели перед запуском. anaschu 27.06.2026 Скрытые отказы в моделях систем динамики (SD-models) экологических систем: два случая из практики Контекст Разбирался прототип модели систем динамики (SD-модели) микоризной сукцессии: пять. . .	Сукцессия 11. Проверка орудий перед войной: разработка через тестирование anaschu 27.06.2026 Как не дать модели соврать самой себе: проверки для симуляции микоризной сукцессии Введение Когда вы строите математическую модель живой системы — грибов, растений, почвы — главная опасность. . .	10 сукцессия. Питон код войны грибов и растений anaschu 27.06.2026 import numpy as np class PlantAgent: def __init__(self, name, strategy, initial_biomass): self. name = name self. strategy = strategy # "greedy" (широколиственные) или. . .

@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