Форум программистов, компьютерный форум 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
26.01.2011, 18:30  [ТС]     Кубики, динамическое программирование
Всем спасибо, я сделал кеш и все стало ок.
Код:
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");
}
 
Текущее время: 04:39. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru