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

Из заданной числовой последовательности выделить монотонно неубывающую подпоследовательность максимально возможной длины - C++

Восстановить пароль Регистрация
 
Рейтинг: Рейтинг темы: голосов - 10, средняя оценка - 4.70
TonyKing
 Аватар для TonyKing
0 / 0 / 0
Регистрация: 16.01.2011
Сообщений: 14
16.01.2011, 11:31     Из заданной числовой последовательности выделить монотонно неубывающую подпоследовательность максимально возможной длины #1
Привет вам, умный народ!
Вынужден обратиться к вам за помощью, ибо прижало!

Проблема у меня с динамическим программированием, а большинству из вас это плевое дело)


Из заданной числовой последовательности выделить монотонно неубывающую подпоследовательность максимально возможной длины. Если таких несколько, то из них нужно выбрать ту, у которой наибольшая сумма чисел.


Вход-выход - ерунда)
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
16.01.2011, 11:31     Из заданной числовой последовательности выделить монотонно неубывающую подпоследовательность максимально возможной длины
Посмотрите здесь:

C++ Найти число последовательности, у которого количество одинаковых цифр максимально
Visual Studio: Вывести номера столбцов матрицы, элементы которых образуют монотонно убывающую или монотонно возрастающую последовательность C++
В заданной последовательности слов найдите все слова, начинающиеся с заданной приставки C++
Обработка числовой последовательности C++
Найти максимально длинные возрастающие последовательности чисел массива C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
16.01.2011, 12:28     Из заданной числовой последовательности выделить монотонно неубывающую подпоследовательность максимально возможной длины #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
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
#include <stdio.h>
 
int main()
{
    int **mas, N, i, j;
    printf("N= ");
    scanf("%d", &N);
    mas=new int*[3];
    for(i=0; i<3; i++)
        mas[i]=new int[N];
    for(i=0; i<N; i++)
        {
            printf("[%d]= ", i);
            scanf("%d", &mas[0][i]);
        }
    mas[1][N-1]=1; mas[2][N-1]=mas[0][N-1];
    for(i=N-2; i>=0; i--)
    {
        mas[1][i]=1; mas[2][i]=mas[0][i];
        for(j=i+1; j<N; j++)
            if(mas[0][i]<=mas[0][j] && mas[1][i]<=mas[1][j]+1)
            {
                if(mas[1][i]==mas[1][j]+1 && mas[2][i]<mas[2][j])
                    mas[2][i]=mas[2][j]+mas[0][i];
                if(mas[1][i]<=mas[1][j]+1)
                {
                    mas[2][i]=mas[2][j]+mas[0][i];
                    mas[1][i]=mas[1][j]+1;
                }
            }
    }
    int i_max=0;
    for(i=1; i<N; i++)
    {
        if(mas[1][i]==mas[1][i_max] && mas[2][i]>mas[2][i_max])
            i_max=i;
        if(mas[1][i]>mas[1][i_max])
            i_max=i;
    }
    int col=mas[1][i_max];
    while(col>0)
    {
        printf("%d ", mas[0][i_max]);
        for(i=i_max+1; i<N; i++)
            if(mas[0][i]>=mas[0][i_max] && mas[1][i]+1==mas[1][i_max] && mas[2][i_max]-mas[0][i_max]==mas[2][i])
            {
                i_max=i;
                break;
            }
            col--;      
    }   
    return 0;
}
TonyKing
 Аватар для TonyKing
0 / 0 / 0
Регистрация: 16.01.2011
Сообщений: 14
16.01.2011, 13:29  [ТС]     Из заданной числовой последовательности выделить монотонно неубывающую подпоследовательность максимально возможной длины #3
valeriikozlov, спасибо большое!
Сейчас буду разбираться)
TonyKing
 Аватар для TonyKing
0 / 0 / 0
Регистрация: 16.01.2011
Сообщений: 14
25.01.2011, 10:06  [ТС]     Из заданной числовой последовательности выделить монотонно неубывающую подпоследовательность максимально возможной длины #4
Код работает не верно.

Например

1 4 2 1 3

Добавлено через 1 час 13 минут
В строчке №25 должно быть < вместо <=
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
25.01.2011, 10:58     Из заданной числовой последовательности выделить монотонно неубывающую подпоследовательность максимально возможной длины #5
TonyKing,
Цитата Сообщение от TonyKing Посмотреть сообщение
В строчке №25 должно быть < вместо <=
Да правильно, и еще строку 23 заменить на:
C
1
                             if(mas[1][i]==mas[1][j]+1 && mas[2][i]<mas[2][j]+mas[0][i])
Yandex
Объявления
25.01.2011, 10:58     Из заданной числовой последовательности выделить монотонно неубывающую подпоследовательность максимально возможной длины
Ответ Создать тему
Опции темы

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