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

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

Восстановить пароль Регистрация
 
c_user
1 / 1 / 0
Регистрация: 13.12.2010
Сообщений: 26
24.01.2011, 23:42     Кубики, динамическое программирование #1
Здраствуйте!
Есть задача ( на украинском)

Код

Незважаючи на те, що Петрик П’яточкін ходить до школи, він все ще продовжує гратися з кубиками. З однакових кубиків він викладає сходинки вздовж стіни. Для цього складає стовпчики з кубиків таким чином:
перший стовпчик стоїть впритул до стіни;
другий стовпчик стоїть впритул до стіни і впритул до першого стовпчика праворуч від нього;
третій стовпчик стоїть впритул до стіни і впритул до другого стовпчика праворуч від нього і так далі...
Висоти стовпчиків не зростають при розгляданні сходинок зліва направо. Інакше кажучи, якщо 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 секунда.

Не подскажите, как еще ее можно решить?
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
24.01.2011, 23:42     Кубики, динамическое программирование
Посмотрите здесь:

Динамическое программирование C++
C++ Динамическое программирование
C++ динамическое программирование
Динамическое программирование C++
C++ Динамическое программирование
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
25.01.2011, 01:47     Кубики, динамическое программирование #2
c_user, привет. Переведи, пожалуйста, на русский, тогда посмотрю.
c_user
1 / 1 / 0
Регистрация: 13.12.2010
Сообщений: 26
26.01.2011, 01:20  [ТС]     Кубики, динамическое программирование #3
Код
Несмотря на то, что Петя Пяточкин ходит в школу, он все еще продолжает играть с кубиками. С одинаковых кубиков он вылаживает ступени вдоль стены. Для этого составляет столбики из кубиков следующим образом: 
первый столбец стоит вплотную к стене; 
второй столбик стоит вплотную к стене и самого первого столбца справа от него; 
третий столбик стоит вплотную к стене и самого второго столбика справа от него и так далее ... 
Высоты столбиков не растут при рассматривании ступенек слева направо. Другими словами, если 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
Добавлено через 7 часов 1 минуту
Никто не знает?
volovzi
266 / 168 / 8
Регистрация: 14.03.2010
Сообщений: 501
26.01.2011, 01:47     Кубики, динамическое программирование #4
Всё равно не понимаю задания. Но я уверен, что здесь чистая комбинаторика. Решить на бумаге, а потом просто запрограммировать формулы.
no0ker
100 / 87 / 4
Регистрация: 17.12.2010
Сообщений: 416
26.01.2011, 09:08     Кубики, динамическое программирование #5
c_user, можете переформулировать задачу своими словами?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
26.01.2011, 09:49     Кубики, динамическое программирование #6
c_user, ссылку на тестирующую систему можете дать?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.01.2011, 18:30     Кубики, динамическое программирование
Еще ссылки по теме:

C++ Динамическое программирование
C++ Динамическое программирование
C++ Динамическое программирование

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

Или воспользуйтесь поиском по форуму:
c_user
1 / 1 / 0
Регистрация: 13.12.2010
Сообщений: 26
26.01.2011, 18:30  [ТС]     Кубики, динамическое программирование #7
Всем спасибо, я сделал кеш и все стало ок.
Код:
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
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
#include <iostream>
#include <vector>
using namespace std;
 
typedef long long int64;
 
 
 
 
int64 cachearray[7][7][7][7][7][7];
 
 
inline void cache_copy(const vector<short> columns, const int64 &new_val)
{
    short addr_array[6];
    for(short i=0; i<6; i++)
    {
        addr_array[i]=(columns.size()>i?columns[i]:0);
    }
    cachearray[addr_array[0]][addr_array[1]][addr_array[2]][addr_array[3]][addr_array[4]][addr_array[5]]=new_val;
 
}
 
inline int64 cached_copy(const vector<short> &columns)
{
    short addr_array[6];
    for(short i=0; i<6; i++)
    {
        addr_array[i]=(columns.size()>i?columns[i]:0);
    }
    return cachearray[addr_array[0]][addr_array[1]][addr_array[2]][addr_array[3]][addr_array[4]][addr_array[5]];
}
 
int64 f(vector<short> columns)
{
    if(columns.size()==1 || columns[0]==1) return 1;
    int64 cached=cached_copy(columns);
    if(cached!=0) return cached;
    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();
            int64 tmpresult=f(tmp_columns);
            cache_copy(tmp_columns, tmpresult);
            result+=tmpresult;
            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);;
    }
    memset(cachearray,0,sizeof(cachearray));
    cachearray[1][0][0][0][0][0]=1;
    cachearray[2][1][0][0][0][0]=2; 
    cachearray[3][2][1][0][0][0]=16;
    cachearray[4][3][2][1][0][0]=768;
    cachearray[5][4][3][2][1][0]=292864;
    memset(cachearray[6][5][4][3][2]+1, 1100742656ll, sizeof(int64) );
    cout<<f(columns)<<endl;
    system("pause>nul");
}
Yandex
Объявления
26.01.2011, 18:30     Кубики, динамическое программирование
Ответ Создать тему
Опции темы

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