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

Кубики, динамическое программирование - C++

Войти
Регистрация
Восстановить пароль
Другие темы раздела
C++ Время выполнения(сложность) http://www.cyberforum.ru/cpp-beginners/thread233622.html
Как вычислить время выполнения программы? и что такое NlogN?
C++ Заменить ing на ed Требуется написать программу на языке С++, заменяющую в строке S окончания -ing на -ed. http://www.cyberforum.ru/cpp-beginners/thread233610.html
Вопрос по рекурсии C++
Добрый вечер. В книжке С++ базовый курс Шилдта стр 175-176 есть пример Отображение строки в обратном порядке с помощью рекурсии (функция reverse) #include <iostream> using namespace std; void reverse (char *s); int main() { char str = "eto test"; reverse (str); return 0;
C++ "М" на "Н"
Требуется написать программу на С++, заменяющюю в строке S все буквы "М" на "Н" и обратно. При отсутствии букв "М" и "Н", должно выдаваться соответствующее сообщение.
C++ Функции пользователя http://www.cyberforum.ru/cpp-beginners/thread233599.html
Функции пользователя Составить программу, которая решает задачу с такими дополнительными условиями: • размерность матрицы должна вводиться при выполнении программы; • само решение задачи должно быть оформлено в виде функции, которой передается матрица и ее размерность. Заполнить матрицу ЛП, от центра по спирали: влево - вниз - вправо - вверх. С ++ пожалуйста
C++ Новичек Что значит выполняется за время NlogN? подробнее

Показать сообщение отдельно
c_user
1 / 1 / 0
Регистрация: 13.12.2010
Сообщений: 26

Кубики, динамическое программирование - C++

24.01.2011, 23:42. Просмотров 956. Ответов 6
Метки (Все метки)

Здраствуйте!
Есть задача ( на украинском)

Код

Незважаючи на те, що Петрик П’яточкін ходить до школи, він все ще продовжує гратися з кубиками. З однакових кубиків він викладає сходинки вздовж стіни. Для цього складає стовпчики з кубиків таким чином:
перший стовпчик стоїть впритул до стіни;
другий стовпчик стоїть впритул до стіни і впритул до першого стовпчика праворуч від нього;
третій стовпчик стоїть впритул до стіни і впритул до другого стовпчика праворуч від нього і так далі...
Висоти стовпчиків не зростають при розгляданні сходинок зліва направо. Інакше кажучи, якщо hi — висота i-го стовпчика, то h1 ≥ h2 ≥ h3 ≥ ... .
Петрик встановлює кубики у деякій послідовності. Він встановив для себе такі правила:
Кубик, розташований не на підлозі, можна поставити лише після кубика, на якому він має стояти. Інакше кажучи, не можна підсовувати кубики під вже поставлені;
Кубик, який знаходиться не у першому стовпчику, можна поставити лише після встановлення кубика, розташованого ліворуч від нього.
Завдання
Знайти кількість різних способів послідовного встановлення кубиків, у результаті яких виникнуть сходи з заданими висотами стовпчиків h1, h2, ... , hk. Враховують лише ті способи, що задовольняють умови 1 і 2.

Вхідні дані
Перший рядок вхідного файлу містить натуральне число k — кількість стовпчиків (1 ≤ k ≤ 6).
Другий рядок вхідного файлу містить k натуральних чисел h1, h2, ... , hk — кількості кубиків відповідно у першому, другому, … , k-му стовпчику сходів (6 ≥ h1 ≥ h2 ≥ ... ≥hk ≥ 1).

Вхідні дані
Єдиний рядок вихідного файлу має містити кількість різних способів розташування кубиків у задану конфігурацію згідно з вказаними правилами 1 і 2 при даних висотах стовпчиків.

Прикладcubes.in	cubes.out
3
2 2 1	                       5

Мое решение:

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
#include <iostream>
#include <vector>
using namespace std;
 
typedef long long int64;
 
int64 f(vector<short> columns)
{
    if(columns.size()==1 || columns[0]==1) return 1;
    int64 result=0;
    short max_floor=0; 
    for(short i=columns.size()-1; i>=0;i--)
    {
        if(columns[i]>max_floor)
        {       
            vector<short> tmp_columns=columns;
            if(tmp_columns[i]>1) tmp_columns[i]--;
            else tmp_columns.pop_back();
            result+=f(tmp_columns);
            max_floor=columns[i];
        }
    }
    return result;
}
int main()
{
    short number_of_columns;
    vector<short> columns;
    //freopen("cubes.in","r",stdin);
    //freopen("cubes.out","w",stdout);
    cin>>number_of_columns;
    for (short i=0; i<number_of_columns; i++)
    {
        short tmp;
        cin>>tmp;
        columns.push_back(tmp);;
    }
    cout<<f(columns)<<endl;
    system("pause>nul");
}
Не улаживается в лимит 1 секунда.

Не подскажите, как еще ее можно решить?
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
 
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru