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

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

Восстановить пароль Регистрация
 
Prim
0 / 0 / 0
Регистрация: 25.04.2013
Сообщений: 3
25.04.2013, 21:55     Динамическое программирование #1
Ограничение по времени: 2 секунды
Ограничение по памяти: 256 мегабайт

У Пети есть полоска бумаги, разделенная на N клеток. Он хочет раскрасить каждую клетку в
синий, красный или зеленый цвет.
Кроме этого, Пете интересны одноцветные отрезки. Петя называет одноцветным отрезком
несколько подряд идущих клеток, раскрашенных в один цвет и ограниченных с обеих сторон клет-
ками другого цвета или границами полоски.
Петя хочет, чтобы все синие одноцветные отрезки имели длину A клеток, все красные одноцвет-
ные отрезки имели длину B клеток, а все зеленые одноцветные отрезки имели длину C клеток.
Пете интересно, сколькими способами он может раскрасить полоску таким образом. Помогите
ему и вычислите это количество. Поскольку оно может быть очень большим, выведите его по модулю 109+7.
Формат входного файла
В первой строке записано четыре целых числа, разделенных пробелами — N, A, B и C
(1<=A; B; C; N<=106, A; B; C<=N).
Формат выходного файла
Выведите ответ на задачу по модулю 109 + 7.
Примеры
3 1 2 3-3
3 1 1 1-12
5 1 1 1-48
3 2 2 2-0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.04.2013, 21:55     Динамическое программирование
Посмотрите здесь:

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

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

Или воспользуйтесь поиском по форуму:
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
ya_noob
_
200 / 144 / 9
Регистрация: 08.10.2011
Сообщений: 432
26.04.2013, 16:41     Динамическое программирование #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
#include <iostream>
#include <vector>
using namespace std;
 
int A, B, C;
vector< vector< int > > v( 3, vector< int >( 1000000 + 1, 0 ) );
 
int mod( int x )
{
    return x % 1000000007;
}
 
int calc( int N, int x = -1 )
{
    if ( N == 0 ) return 1;
 
    int sum = 0;
 
    if ( x != 0 && N >= A )
        sum = mod( sum + ( v[ 0 ][ N - A ] > 0 ? v[ 0 ][ N - A ] : v[ 0 ][ N - A ] = calc( N - A, 0 ) ) );
    if ( x != 1 && N >= B )
        sum = mod( sum + ( v[ 1 ][ N - B ] > 0 ? v[ 1 ][ N - B ] : v[ 1 ][ N - B ] = calc( N - B, 1 ) ) );
    if ( x != 2 && N >= C )
        sum = mod( sum + ( v[ 2 ][ N - C ] > 0 ? v[ 2 ][ N - C ] : v[ 2 ][ N - C ] = calc( N - C, 2 ) ) );
 
    return sum;
}
 
int main()
{
    int N;
    
    cin >> N >> A >> B >> C;
    cout << calc( N ) << endl;
 
    return 0;
}
но ее слабость в том, что она рекурсивная. Для больших N (например, для входа "44000 1 1 1") системного стека не хватает и программа падает. Надо бы перенести ее на явный стек, но мне лень. Идею решения я написал, дальше думай сам.

Добавлено через 3 часа 14 минут
я тут подумал что проблему со стеком можно решить с помощью восходящего динамического программирования, переписал программу и всё заработало. теперь и для миллиона считает.
Prim
0 / 0 / 0
Регистрация: 25.04.2013
Сообщений: 3
26.04.2013, 19:17  [ТС]     Динамическое программирование #3
Большое спасибо, буду разбираться.
Yandex
Объявления
26.04.2013, 19:17     Динамическое программирование
Ответ Создать тему
Опции темы

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