Форум программистов, компьютерный форум CyberForum.ru

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.62
SoulC++
0 / 0 / 0
Регистрация: 27.09.2011
Сообщений: 13
#1

C++, Задача про лесенку, помогите пожалуйста. - C++

29.09.2011, 19:03. Просмотров 1865. Ответов 1
Метки нет (Все метки)

Лесенка
На каждой из n + 2 ступенек лестницы записано целое число, причем на первой и на последней ступеньке записано число 0. На первой ступеньке стоит человек, которому необходимо подняться на последнюю ступеньку. За один шаг он может подниматься на любое число ступенек, не превосходящее k.

Подсчитаем сумму всех чисел, написанных на ступеньках, на которые наступил человек. Найдите наибольшее возможное значение этой суммы.

Пример входных данных
3
1 -1 1
2
Пример выходных данных
2

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <stdio.h>
#include <algorithm>
using namespace std;
 
int n, k, i, j;
int a[100001];
int main () {
    scanf("%d", &n);
    for(i = 0; i < n; i++)
        a[i] = 0;
    for(i = 1; i <= n; i++)
        scanf("%d", &a[i]);
    scanf("%d", &k);
    for(i = n; i >= 1; i--)
        for(j = i+1; j < i+k; j++)
            a[i] += max(a[j], a[j++]);
    
    
    
    printf("%d\n", a[1]);
    return 0;
}
вроде все верно, но где промах?Идея не та? Или путаница в указателях?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
29.09.2011, 19:03     C++, Задача про лесенку, помогите пожалуйста.
Посмотрите здесь:
C++ Подсчитать суммарное количество подтягиваний в лесенку. Работа с файлами.
C++ Расскажите пожалуйста про флаги
Обясните пожалуйста все про классы в С++ C++
Исправьте прогу, пожалуйста! Прога про массивы.... C++
C++ Помогите с задачей про списки.
C++ Подскажите пожалуйста где можно почитать про структуры
Поясните, пожалуйста, несколько моментов про выделение памяти C++
C++ Задача про водопровод
задача про МКАД C++
Задача про 2 рюкзака C++
Задача про птичек C++
C++ Задача про год

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
4669 / 2495 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
30.09.2011, 06:07     C++, Задача про лесенку, помогите пожалуйста. #2
Цитата Сообщение от SoulC++ Посмотреть сообщение
Идея не та?
идея не та.

Цитата Сообщение от SoulC++ Посмотреть сообщение
for(i = n; i >= 1; i--)
for(j = i+1; j < i+k; j++)// вот тут сразу же при i==n идет выход за границы массива
a[i] += max(a[j], a[j++])
Но не это самое главное. Даже если Вы исправите выход за границу массива у Вас все равно ничего не получится. Ведь в этой строке:
Цитата Сообщение от SoulC++ Посмотреть сообщение
a[i] += max(a[j], a[j++]);
Вы изменяете значение самой ступеньки a[i] и дальнейший результат у Вас абсолютно никак не зависит от значений ступенек.
Для расчета результата (в том числе и промежуточного) заводите второй масив.
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru