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

Вычеркнуть минимальное количество чисел, чтобы оставшиеся шли в порядке возрастания (дин. программирование) - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Переставить слова из файла в обратном порядке http://www.cyberforum.ru/cpp-beginners/thread1671261.html
Задание звучит так : Дан файл с неизвестным количеством слов и строк.Создать новый файл каждая строка которого получается из соответствующей строки исходящего файла перестановкой слов в обратном порядке. Вывести буквы задом наперед у меня получилось , но без пробелов и это не то что требуется.Помогите.Спасибо.
C++ Написать программу, которая будет генерировать квадратную матрицу рандомно Необходимо написать программу которая будет генерировать квадратную матрицур рандомно размерности от 3 до 5(рандомно), значения генерируются в пределах от -20 до 20. http://www.cyberforum.ru/cpp-beginners/thread1671257.html
Перевод вектора в последовательность C++
Добрый день, где-то в глубине души понимаю, что нельзя основываясь на переменою времени выполнения( std::vector<void(*) > arr; ) определить построения кода на этапе компиляции( void sequence( Args... args) ). Но всё же программисты могут всё ) Вопрос: Как меняя только код в main собрать в вектор execut`оры и вызвать через сигнатуру void sequence( Args... args) их как функторы ...
C++ Определить количество видеокарт
Здравствуйте, уважаемые форумчане! Необходимо используя средстава С++ определить количество установленых видеокарт и поддерживаемых ими графических режимов (разрешение экрана, битность и т.д.).
C++ Получить слово, образованное k-ыми символами каждой строки http://www.cyberforum.ru/cpp-beginners/thread1671214.html
Дан текстовый файл. Получить слово, образованное k-ыми символами каждой строки. Собственно написал что то, но разбивку строки на предложения я делаю неправильно. Не знаю можно ли использовать функцию стрток в типе стринг, скорее всего нет и надо эту часть изменить. Помогите пожалуйста. #include "fstream" #include "string" #include "iostream" using namespace std; int main()
C++ Реализовать функцию нахождения определителя квадратной матрицы заданного размера Необходимо написать программу, матрица 3 на 3, найти чему равен определитель. Реализовать используя функцию. подробнее

Показать сообщение отдельно
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,691
27.02.2016, 07:58     Вычеркнуть минимальное количество чисел, чтобы оставшиеся шли в порядке возрастания (дин. программирование)
Вариант без двумерного массива:
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
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
//Написать программу, которая использует метод динамического программирования. Даны N
//целых чисел X1,X2, . . . ,XN (1 <= N <= 10000, 1 <= Xi <= 60000). Требуется вычеркнуть
//из них минимальное количество чисел так, чтобы оставшиеся шли в порядке возрастания.
//Пример.
//Ввод: 2 5 3 4 6 1
//Вывод: 2 3 4 6
///////////////////////////////////////////////////////////////////////////////
#include <algorithm>
#include <cstdlib>
#include <ctime>
#include <deque>
#include <iostream>
#include <iterator>
///////////////////////////////////////////////////////////////////////////////
typedef std::deque  < int   >   T_numbers;
///////////////////////////////////////////////////////////////////////////////
template< typename  TT_cont >
void    print_cont( TT_cont     const   &   cont )
{
    std::copy
        (
            cont.begin                                              (),
            cont.end                                                (),
            std::ostream_iterator< typename TT_cont::value_type >   ( std::cout, "\t" )
        );
 
    std::cout   <<  std::endl;
}
///////////////////////////////////////////////////////////////////////////////
void    set_longest_increasing_subsequence
    (
        T_numbers   const   &   numbers,
        T_numbers           &   subsequence
    )
{
    int         numbers_size    =   numbers.size();
    T_numbers   seq_lens            ( numbers_size, 1 );
    T_numbers   prev_indexes        ( numbers_size );
    int         seq_len_max         {1};
    int         last_ind            {};
 
    for( int  i{1}; i < numbers_size; ++i )
    {
        for( int  j{}; j < i; ++j )
        {
            if  (
                            numbers[j]
                        <   numbers[i]
 
                    &&      seq_lens[j] + 1
                        >   seq_lens[i]
                )
            {
                seq_lens        [i]     =   seq_lens[j] + 1;
                prev_indexes    [i]     =   j;
 
                if  (
                            seq_lens[i]
                        >   seq_len_max
                    )
                {
                    seq_len_max     =   seq_lens[i];
                    last_ind        =   i;
                }
            }//if
        }//for j
    }//for i
 
    while   (
                    int(    subsequence.size()  )
                <   seq_len_max
            )
    {
        subsequence.push_front
            (
                numbers[ last_ind ]
            );
 
        last_ind   =   prev_indexes[ last_ind ];
    }
}
///////////////////////////////////////////////////////////////////////////////
int     main()
{
    srand(unsigned(time(0)));
 
    for(;;)
    {
        int         num_size    =   rand() % 10 + 1;
        T_numbers   numbers;
 
        for( int  i = 0; i < num_size; ++i )
        {
            numbers.push_back( rand() % 10 + 1 );
        }
 
        print_cont  ( numbers );
        T_numbers   subsequence;
 
        set_longest_increasing_subsequence
            (
                numbers,
                subsequence
            );
 
        print_cont( subsequence );
        system("pause");
    }//for
}
 
Текущее время: 18:01. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru