Форум программистов, компьютерный форум 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() Не могу ничего найти про эту процедуру. Кто-нибудь может подсказать, что она делает и с ккими параметрами работает? подробнее

Показать сообщение отдельно
SlavaSSU
215 / 160 / 45
Регистрация: 17.07.2012
Сообщений: 587
02.12.2014, 10:52     Динамическое программирование: самая длинная строго возрастающая подпоследовательность
C++ (Qt)
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
#include <iostream>
 
using namespace std;
 
const int N = 1000;
 
int a[N];
int dp[N];
int n;
 
int main(){
 
    cin >> n;
    for(int i = 0; i < n; i++)
        cin >> a[i], dp[i] = 1;
 
    for(int i = 0; i < n; i++)
    {
        for(int j = i + 1; j < n; j++)
            if(a[j] > a[i])
                dp[j] = max(dp[j], dp[i] + 1);
    }
 
    int ans = 0;
    for(int i = 0; i < n; i++)
        ans = max(ans, dp[i]);
 
    cout << ans << endl;
 
    return 0;
}
Добавлено через 19 минут
Fallenworld,

50
411 915 930 547 328 51 446 45 281 631 703 953 129 188 689 386 901 129 317 156 42 339 255 2 541 0 937 584 657 205 423 58 924 687 409 723 586 430 772 246 961 518 65 705 451 413 893 533 376 471


ответ == 12.

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