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

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

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 13, средняя оценка - 4.62
SoulC++
0 / 0 / 0
Регистрация: 27.09.2011
Сообщений: 13
29.09.2011, 19:03     C++, Задача про лесенку, помогите пожалуйста. #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++ Задача про яйца

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 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] и дальнейший результат у Вас абсолютно никак не зависит от значений ступенек.
Для расчета результата (в том числе и промежуточного) заводите второй масив.
Yandex
Объявления
30.09.2011, 06:07     C++, Задача про лесенку, помогите пожалуйста.
Ответ Создать тему
Опции темы

Текущее время: 08:59. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru