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

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

Войти
Регистрация
Восстановить пароль
 
Prim
0 / 0 / 0
Регистрация: 25.04.2013
Сообщений: 3
#1

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

25.04.2013, 21:55. Просмотров 764. Ответов 2
Метки нет (Все метки)

Ограничение по времени: 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
0
Надоела реклама? Зарегистрируйтесь и она исчезнет полностью.
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
25.04.2013, 21:55
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Динамическое программирование (C++):

Динамическое программирование - C++
Есть такая задача: Дана схема стены, необходимо проверить можно ли построить данную стену заданным набором кирпичей. Кирпич высот 1, а...

Динамическое программирование! - C++
#include &lt;cstdio&gt; #include &lt;algorithm&gt; using namespace std; int a, n, m; int main() { scanf(&quot; %d %d&quot;, &amp;n,...

Динамическое программирование - C++
Помогите решить задачу! Я что-то особо не соображу... 1.Написать программу, реализующую действия: а. сформировать ленточную матрицу...

Динамическое программирование - C++
Усложнили задачу мне.... : Дан массив A. Необходимо найти максимальную сумму элементов прямоугольного подмассива по всем возможным...

Динамическое программирование - C++
Столкнулся с такой задачей. Есть 6 фигурок площадью 3. Нужно узнать, сколькими способами можно полностью замостить ими поле n на m,...

Динамическое программирование - C++
Задача: Есть n работников и n работ. Необходимо найти максимальную суммарную производительность. Каждый работник может выполнять только...

2
ya_noob
_
202 / 146 / 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 минут
я тут подумал что проблему со стеком можно решить с помощью восходящего динамического программирования, переписал программу и всё заработало. теперь и для миллиона считает.
1
Prim
0 / 0 / 0
Регистрация: 25.04.2013
Сообщений: 3
26.04.2013, 19:17  [ТС] #3
Большое спасибо, буду разбираться.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
26.04.2013, 19:17
Привет! Вот еще темы с ответами:

Динамическое программирование - C++
На расстоянии n шагов от магазина стоит А. Каждую минуту он выбирает куда сделать шаг: к магазину или в противоположном направлении. ...

Динамическое программирование - C++
народ помогите пожалуйста. есть задача Написать программу, позволяющую вычислить количество чисел, не содержащих нули, сумма цифр...

ДП Динамическое программирование - C++
ограничение времени на тест: 0.5 сек. ограничение памяти на тест: 65536 KB. Рассмотрим все строки длины N, состоящие только из букв...

Динамическое программирование - C++
Подскажите что не так в решении. #include &lt;iostream&gt; #include &lt;stdio.h&gt; using namespace std; const int N = 5001; int...


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

Или воспользуйтесь поиском по форуму:
3
Ответ Создать тему
Опции темы

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