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

Динамическое программирование: самая длинная строго возрастающая подпоследовательность - C++

Восстановить пароль Регистрация
Другие темы раздела
C++ Std::thread автоматическая многопоточность http://www.cyberforum.ru/cpp-beginners/thread1311270.html
Есть данный пример создания массива thread и инициализации его в цикле. #include<iostream> #include<sstream> #include<thread> using namespace std; class printId { public: void operator()() { ostringstream out;
C++ Скопировать в текстовой файл слова содержащие символ 'C' Дан символ C — строчная (маленькая) латинская буква и текстовый файл. Создать строковый файл и записать в него все слова из исходного файла, содержащие хотя бы одну букву C (прописную или строчную). Словом считать набор символов, не содержащий пробелов, знаков препинания и ограниченный пробелами, знаками препинания или началом/концом строки. Если исходный файл не содержит подходящих слов, то... http://www.cyberforum.ru/cpp-beginners/thread1311264.html
C++ Как ускорить пирамидальную сортировку?
Второй цикл for в пирамидальной сортировке можно было бы сократить, добавив условие завершения i > 3. Следует ли добавить после этого цикл, и если да, то что, для того, чтобы конечный список как и раньше был отсортированным? Приводят ли подобные изменения к уменьшению числа сравнений?
Написать программу: Определить разность между наибольшей и наименьшей цифрами натурального числа C++
Напишите код. Определить разность между наибольшей и наименьшей цифрами натурального числа N, представленного в шестиричной системе счисления.
C++ Написать программу: могут ли три числа быть длинами сторон треугольника? http://www.cyberforum.ru/cpp-beginners/thread1311253.html
Решите эту задачу: даны три числа если они могут быть длинами сторон равнобедренного тупоугольного треугольника, то вычислите его площадь. Выведите длины сторон и площадь в порядке возрастания значений.
C++ Rnunif() Не могу ничего найти про эту процедуру. Кто-нибудь может подсказать, что она делает и с ккими параметрами работает? подробнее

Показать сообщение отдельно
Fallenworld
76 / 76 / 9
Регистрация: 14.04.2014
Сообщений: 408
02.12.2014, 10:19     Динамическое программирование: самая длинная строго возрастающая подпоследовательность
SlavaSSU, да, не учел, что куски последовательностей могут быть общими.

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
#include <iostream>
#include <string.h>
#include <stdio.h>
#include <vector>
 
using namespace std;
template<typename T>
bool find_podposled(const T& arg, vector< vector<T> > &posled){
    bool newPodposl(false);
    for(unsigned int j=0; j < posled.size(); ++j) //есть ли подпос-ть для arg?
        if(arg>(posled[j]).back()){
            (posled[j]).push_back(arg);
            newPodposl  = true;
        }
    return newPodposl;
}
 
 
int main(){
 
    const int n=50;
    int N[n]{12, 24, 42, 43, 36, 3, 40, 29, 7, 34, 10, 13, 28, 9,
        35, 23, 25, 21, 19, 4, 20, 18, 11, 38, 41, 48, 6, 46, 33,
        17, 31, 37, 2, 30, 32, 44, 45, 5, 47, 49, 16, 15, 50, 27, 26, 14, 39, 22, 1, 8};
 
 
 
 
    vector<vector<int> > podposlovatelnosti(1);
    (podposlovatelnosti.back()).push_back(N[0]);
 
    for(int i=1; i<n; ++i){
 
        if(!find_podposled(N[i],podposlovatelnosti)){
            //надо делать новую. Найдем самую длинную из новых
            //хотя нет, создадим все варианты
            vector<int> podposl;
            bool newpodposl(false);
            unsigned int size = podposlovatelnosti.size();
            for(unsigned int j=0, k=0; j < size; ++j,k=0){
 
                while((podposlovatelnosti[j])[k] < N[i])
                    podposl.push_back((podposlovatelnosti[j])[k++]);
 
                if(podposl.size()) {
                    podposl.push_back(N[i]);
                    //if(podposl!=podposlovatelnosti.back()){
                    if(podposlovatelnosti.size()>size){
                        k=size;
                        while(k<podposlovatelnosti.size()){
                            if(podposlovatelnosti[k]==podposl){
                                podposl.clear();
                                break;
                            }
 
                            ++k;
                        }
                         if(!podposl.size()) continue;
                    }
                    podposlovatelnosti.push_back(podposl);
                    newpodposl = true;
                    podposl.clear();
                }
 
            }
            if(!newpodposl){
                podposl.push_back(N[i]);
                podposlovatelnosti.push_back(podposl);
            }
        }
    }
 
    unsigned int max(0), num(0);
    for(unsigned int i=0; i<podposlovatelnosti.size(); ++i)
        if(max<podposlovatelnosti[i].size()){
            max = podposlovatelnosti[i].size();
            num = i;
        }
    for(unsigned int i=0; i<podposlovatelnosti[num].size(); ++i) cout<<(podposlovatelnosti[num])[i]<<"  ";
    return 0;
 
}
523 подпос.
 
Текущее время: 22:23. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru