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

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

Войти
Регистрация
Восстановить пароль
 
 
Рейтинг: Рейтинг темы: голосов - 19, средняя оценка - 4.79
newyork7776
349 / 342 / 80
Регистрация: 21.05.2013
Сообщений: 1,311
Завершенные тесты: 1
#1

Платная лестница - C++

10.11.2013, 00:30. Просмотров 2901. Ответов 24
Метки нет (Все метки)

Мальчик подошел к платной лестнице. Чтобы наступить на любую ступеньку, нужно заплатить указанную на ней сумму. Мальчик умеет перешагивать на следующую ступеньку, либо перепрыгивать через ступеньку. Требуется узнать, какая наименьшая сумма понадобится мальчику, чтобы добраться до верхней ступеньки.
В первой строке входного файла вводится одно натуральное число N100 — количество ступенек.
В следующей строке вводятся N натуральных чисел, не превосходящих 100 — стоимость каждой ступеньки (снизу вверх).

Выведите одно число — наименьшую возможную стоимость прохода по лесенке.

пример
3
1 2 3
ответ 4
0
Миниатюры
Платная лестница  
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
10.11.2013, 00:30
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Платная лестница (C++):

лестница - C++
int phi(int n) {int a; a=1; a=2; if (n==1) return a; else a=phi(a+n-1); } как правльно выти из этой рекурсии? алгоритм...

Неправильная лестница на с++ - C++
Нужно сделать лестницу из n-ых элементов чтобы она выгледила вот так : 5 4 5 3 4 5 2 3 4 5 1 2 3 4 5 у меня получилось...

Определить сколькими различными способами можно подняться на заданную ступеньку (Лестница в Небо) - C++
Определить сколькими различными способами можно подняться на десятую ступеньку, если за шаг можно подняться следующую или через одну. Как...

Лестница - Turbo Pascal
Человек поднимается по лестнице один марш которых содержит N ступенек. За один шаг человек может подняться на 1 или 2, или на 3 ... или на...

Лестница - Pascal
Дано натуральное число n.Человек должен подняться по лестнице,имеющей n ступеней.Зная что с каждым шагом он может ступать на каждую ...

Олимпиадная задача. Лестница из кубиков. - Pascal
1) Мальчик Петя строит из кубиков лестницу. Лестница представляет собой несколько стоящихся рядом башенок из кубиков, каждая из которых...

Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
newyork7776
349 / 342 / 80
Регистрация: 21.05.2013
Сообщений: 1,311
Завершенные тесты: 1
10.11.2013, 15:07  [ТС] #16
а если n==1?
0
salam
163 / 144 / 12
Регистрация: 10.07.2012
Сообщений: 728
10.11.2013, 15:10 #17
Цитата Сообщение от newyork7776 Посмотреть сообщение
а если n==1?
то вы сразу прыгаете на первую ступеньку, и все хорошо. у вас числа все натуральные, следовательно добавление любого лишнего шага к оптимальному пути будет вести к тому, что он станет совсем не оптимальным.
0
newyork7776
349 / 342 / 80
Регистрация: 21.05.2013
Сообщений: 1,311
Завершенные тесты: 1
10.11.2013, 15:17  [ТС] #18
Кликните здесь для просмотра всего текста
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
#include <iostream>
#include <vector>
using namespace std;
int minimalne(int a, int b)
{
    if (a>=b) {return b;}
    else return a;
}
int main()
{   
    vector <int> v;
    int n,k;
    int sum=0;
    cin >> n;
    if (n!=0){
    int* ans = new int[n];
    for(int i=0;i<n;i++)
    {   
        ans[i]=0;
        cin >> k;
        v.push_back(k);
    }
    for (int i=0;i<n;i++)
    {
        if (i==0) {ans[i]=v[i];};
        if (i==1) {ans[i]=v[i]+ans[i-1];};
        if (i>1) {ans[i]=minimalne(ans[i-1],ans[i-2])+v[i];};
    }
    cout <<ans[n-1] << "\n";}
}

вот я кидаю свой код на сайт вот задание

Добавлено через 38 секунд
Кликните здесь для просмотра всего текста
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
#include <iostream>
#include <vector>
using namespace std;
int minimalne(int a, int b)
{
    if (a>=b) {return b;}
    else return a;
}
int main()
{   
    vector <int> v;
    int n,k;
    int sum=0;
    cin >> n;
    if (n!=0){
    int* ans = new int[n];
    for(int i=0;i<n;i++)
    {   
        ans[i]=0;
        cin >> k;
        v.push_back(k);
    }
    for (int i=0;i<n;i++)
    {
        if (i==0) {ans[i]=v[i];};
        if (i==1) {ans[i]=v[i]+ans[i-1];};
        if (i>1) {ans[i]=minimalne(ans[i-1],ans[i-2])+v[i];};
    }
    cout <<ans[n-1] << "\n";}
}

результат
Тест Статус Время работы Астрономическое время работы Используемая память
1 Неправильный ответ 0 0.017 1306624
2 OK 0 0.019
3 Неправильный ответ 0 0.003 4096
4 Неправильный ответ 0 0.004 4096
5 Неправильный ответ 0.004 0.004 4096
6 OK 0.004 0.004 4096
7 OK 0 0.003 4096
8 Неправильный ответ 0 0.004 4096
9 Неправильный ответ 0 0.003 4096
10 Неправильный ответ 0.004 0.021 1298432
11 OK 0 0.011 4096
12 OK 0 0.004 4096
13 Неправильный ответ 0.004 0.004 4096
14 Неправильный ответ 0.004 0.003 4096

Добавлено через 2 минуты
1
Кликните здесь для просмотра всего текста
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
#include <iostream>
#include <vector>
using namespace std;
 
int main()
{
    
    
    int n;
    int k;
    vector <int> v;
    cin >> n;
    int* MinE = new int[n];
 
 
    for(int i=0;i<n;i++)
    {
        cin >> k;
        v.push_back(k);
    }
 
    MinE[0]=0;
    MinE[1]=v[0];
    int E1,E2;
    for (int i=2;i<n;i++)
    {
        E1=(v[i]+v[i-1]);
        E2=(v[i]+v[i-2]);
 
        if (E1+MinE[i-1]<E2+MinE[i-2])
            MinE[i]=E1+MinE[i-1];
        else 
            MinE[i]=E2+MinE[i-2];
    }
 
    cout << MinE[n-1] << "\n";
}
Кликните здесь для просмотра всего текста
Тест Статус Время работы Астрономическое время работы Используемая память
1 Неправильный ответ 0 0.003 1306624
2 Неправильный ответ 0 0.003 1306624
3 Неправильный ответ 0 0.003 1306624
4 Неправильный ответ 0 0.004 1306624
5 Неправильный ответ 0.004 0.004 1298432
6 Неправильный ответ 0.004 0.004 1306624
7 Неправильный ответ 0 0.004 1306624
8 Неправильный ответ 0 0.004 1306624
9 Неправильный ответ 0 0.004 1306624
10 OK 0.004 0.003 1298432
11 OK 0 0.004 1306624
12 OK 0.004 0.004 1306624
13 Неправильный ответ 0.004 0.003 1306624
14 Неправильный ответ 0 0.003 1306624

2
Кликните здесь для просмотра всего текста
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 <iostream>
#include <vector>
using namespace std;
 
int main()
{
    
    
    int n;
    int k;
    vector <int> v;
    cin >> n;
    int* MinE = new int[n];
    for(int i=0;i<n;i++)
    {
        cin >> k;
        v.push_back(k);
    }
    if (n>2){
    MinE[0]=0;
    MinE[1]=v[0];
    int E1,E2;
    for (int i=2;i<n;i++)
    {
        E1=(v[i]+v[i-1]);
        E2=(v[i]+v[i-2]);
 
        if (E1+MinE[i-1]<E2+MinE[i-2])
            MinE[i]=E1+MinE[i-1];
        else 
            MinE[i]=E2+MinE[i-2];
    }
 
    cout << MinE[n-1] << "\n";}
    else 
    {
        if (n==1) cout << v[0];
        if (n==2)
        {
            if (v[0]>=v[1]) cout << v[1];
            else cout << v[0];
        }
    }
}


Добавлено через 1 минуту
я уже много вариантов перепробовал но результата не найшол
0
salam
163 / 144 / 12
Регистрация: 10.07.2012
Сообщений: 728
10.11.2013, 15:19 #19
newyork7776, этот код проходит все тесты. сравните.

C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
int main()
{
    int n;
    cin >> n;
    vector<int> ans(n), cost(n);
    for(int i=0; i < n; ++i)
        cin >> cost[i];
    ans[0] = cost[0];
    ans[1] = cost[1];
    for(int i=2; i < n; ++i)
        ans[i] = min(ans[i-1], ans[i-2]) + cost[i];
    cout << ans[n-1] << endl;
    return 0;
}
0
newyork7776
349 / 342 / 80
Регистрация: 21.05.2013
Сообщений: 1,311
Завершенные тесты: 1
10.11.2013, 15:21  [ТС] #20
Кликните здесь для просмотра всего текста
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
using namespace std;
int minimalne(int a, int b)
{
    if (a>=b) {return b;}
    else return a;
}
int main()
{
    int n;
    cin >> n;
    vector<int> ans(n), cost(n);
    for(int i=0; i < n; ++i)
        cin >> cost[i];
    ans[0] = cost[0];
    ans[1] = cost[1];
    for(int i=2; i < n; ++i)
        ans[i] = minimalne(ans[i-1], ans[i-2]) + cost[i];
    cout << ans[n-1] << endl;
    return 0;
}
Кликните здесь для просмотра всего текста
Тест Статус Время работы Астрономическое время работы Используемая память
1 Неправильный ответ 0 0.017 1306624
2 OK 0 0.019
3 Неправильный ответ 0 0.003 4096
4 Неправильный ответ 0 0.004 4096
5 Неправильный ответ 0.004 0.004 4096
6 OK 0.004 0.004 4096
7 OK 0 0.003 4096
8 Неправильный ответ 0 0.004 4096
9 Неправильный ответ 0 0.003 4096
10 Неправильный ответ 0.004 0.021 1298432
11 OK 0 0.011 4096
12 OK 0 0.004 4096
13 OK 0.004 0.004 4096
14 Неправильный ответ 0.004 0.003 4096
0
salam
163 / 144 / 12
Регистрация: 10.07.2012
Сообщений: 728
10.11.2013, 15:26 #21
я ничего не понимаю. только что 100 баллов получил за это.
C++
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#include <iostream>
#include <vector>
using namespace std;
int minimalne(int a, int b)
{
    if (a>=b) {return b;}
    else return a;
}
int main()
{
    int n;
    cin >> n;
    vector<int> ans(n), cost(n);
    for(int i=0; i < n; ++i)
        cin >> cost[i];
    ans[0] = cost[0];
    ans[1] = cost[1];
    for(int i=2; i < n; ++i)
        ans[i] = minimalne(ans[i-1], ans[i-2]) + cost[i];
    cout << ans[n-1] << endl;
    return 0;
}
1
newyork7776
349 / 342 / 80
Регистрация: 21.05.2013
Сообщений: 1,311
Завершенные тесты: 1
10.11.2013, 15:27  [ТС] #22
я тоже не понимаю как?
0
salam
163 / 144 / 12
Регистрация: 10.07.2012
Сообщений: 728
10.11.2013, 15:28 #23
попробуйте сдать код из моего последнего комментария. ) мне интересно, что будет.
0
newyork7776
349 / 342 / 80
Регистрация: 21.05.2013
Сообщений: 1,311
Завершенные тесты: 1
10.11.2013, 15:30  [ТС] #24
пашет 100 балов

Добавлено через 7 секунд
а мой почему нет?
0
salam
163 / 144 / 12
Регистрация: 10.07.2012
Сообщений: 728
10.11.2013, 15:33 #25
потому что разница, которая между ними есть, накладывает отпечаток.
это не столь важно. разберитесь, как и почему это работает.
динамическое программирование - очень важный метод.
1
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
10.11.2013, 15:33
Привет! Вот еще темы с ответами:

GlMaterial c GL_SPECULAR проявляет артефакты (лестница) - OpenGL
OpenGL 1.2 самый обычный, без шейдеров и всяких там расширений. Нарисовал эскиз глобуса, стал экспериментировать с освещением и...

Платная подписка - Joomla
Можно ли сделать платную регистрацию на joomla с ежемесячной оплатой? Какие есть расширения?

Платная IDE - Basic
Здравствуйте. Я тут написал небольшую IDE для FreeBasic'а. IDE удобная и стильная, есть пресеты, подсветка синтаксиса, мультитаб. Сама IDE...

платная регистрация - WordPress
всем привет. в двух словах почему я залез в такие дебри. на сайте работает плагин, который скрывает от незарегистрированных пользователей...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
10.11.2013, 15:33
Ответ Создать тему
Опции темы

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