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

Последовательность - C++

Восстановить пароль Регистрация
 
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
01.11.2011, 17:51     Последовательность #1
Помогите разобраться, исправить код. не понимаю в чем дело
272. Максимальная красивая подпоследовательность

ограничение времени на тест: 0.5 сек.
ограничение памяти на тест: 65536 KB.
ввод: standard
вывод: standard


Дана последовательность N целых чисел A[1], A[2], ..., A[N]. Подпоследовательность называется красивой, если любые два ее элемента имеют разность индексов в первоначальной последовательности не менее D.
Формально, пусть A[i1], A[i2], ..., A[ik] - подпоследовательность длины k, тогда она будет красивой, если i2 - i1 >= D и i3 - i2 >= D и ... и ik - ik-1 >= D.
Найдите максимальную сумму элементов среди всех красивых подпоследовательностей заданной последовательности.

Входные данные
В первой строке входного файла заданы натуральные числа N и D (2 <= N <= 1000; 1 <= D <= N - 1). В следующей строке находятся N целых чисел A[i] (1 <= A[i] <= 10000).

Выходные данные
В результирующем файле должно находится искомое целое число.

Пример

Ввод
5 3
4 2 5 1 7

Вывод
11

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
#include <iostream>
 
typedef long long ll;
 
int main()
{
    int n; ll d;
    std::cin >> n >> d;
    int a[n + 1];
    int z[n + 1];
    
    for (int i = 1; i <= n; ++i)
        std::cin >> a[i];
    
    z[0] = 0;
    for (int i = 1; i <= n; ++i)
    {
        z[i] = std::max(z[i-  ], a[i]);
        std::cout << "i is " << i << " z[i] is " << z[i] << std::endl;
        for (int j = 1; j < i - d; ++j)
        {
            std::cout << "j is " << j << " z[i] is " << z[i] << " z[" << i - d - 1 << "] is " << z[i - d - 1] << " a[j] is " << a[j] << std::endl;
            z[i] = std::max(z[i], z[i - d - 1] + a[i]);
            std::cout << "i-d-i is " << i - d - 1 << " and z[i] now is " << z[i] << std::endl;
        }
    }
    
    ll max = z[0];
    
    for (int i = 1; i <=n; ++i)
        if (max < z[i])
            max = z[i];
    
    std::cout << max << std::endl;
    return 0;
}
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
01.11.2011, 17:51     Последовательность
Посмотрите здесь:

Последовательность C++
Преобразовать литерную последовательность в другую литерную последовательность всеми описанными ниже способами C++
Вводится последовательность из N целых чисел. Сформировать последовательность, C++
C++ Вводить последовательность вещественных чисел, пока следующее вводимое число не окажется меньше предыдущего. Вывести полученую последовательность.
Последовательность С++ C++
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
01.11.2011, 18:57     Последовательность #2
Montanaa, задача очень простая - на динамику.
Исправлять код не буду (особенно 18 строчку), проще написать свой код. Или может быть проще описать алгоритм? Выбирайте...
Montanaa
5 / 5 / 1
Регистрация: 21.03.2011
Сообщений: 79
01.11.2011, 19:50  [ТС]     Последовательность #3
Цитата Сообщение от valeriikozlov Посмотреть сообщение
Montanaa, задача очень простая - на динамику.
Исправлять код не буду (особенно 18 строчку), проще написать свой код. Или может быть проще описать алгоритм? Выбирайте...
А можно свой код?) Буду очень признателен! Заранее огромное спасибо!

Добавлено через 23 минуты
Сможете?
И в 18 строчке i - 1

Добавлено через 6 минут
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
#include <iostream>
 
const int MAXN = 3000;
typedef long long ll;
 
int main()
{
        int n; ll d;
        std::cin >> n >> d;
        int arr[MAXN];
        int z[MAXN];
        
        for (int i = 1; i <= n; ++i)
                std::cin >> arr[i];
        
        z[0] = 0;
        for (int i = 1; i <= n; ++i)
        {
                z[i] = std::max(z[i - 1], arr[i]);
                for (int j = 1; j < i - d; ++j)
                {
                        z[i] = std::max(z[i], z[i - d - 1] + arr[i]);
                }
        }
        
        ll max = z[0];
        
        for (int i = 1; i <=n; ++i)
                if (max < z[i])
                        max = z[i];
        
        std::cout << max << std::endl;
        return 0;
}
Помогите исправить код, я не знаю, что нужно исправлять (

Добавлено через 5 минут
Или если можно свой код, если вам не трудно..
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
01.11.2011, 19:55     Последовательность #4
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
#include <iostream>
 
using namespace std;
 
int main()
{
        int n, d, i, j, max;
        cin >> n >> d;
        int a[1000];
        int z[1000];
        
        for (i = 0; i <n; ++i)
                cin >> a[i];
        for(i=0; i<d-1; i++)
            z[i]=a[i];
        for(i=d-1; i<n; i++)
        {
            max=0;
            if(i-d*2+1>=0)
                j=i-d*2+1;
            else
                j=0;
            for(; j<=i-d; j++)
                if(z[j]>max)
                    max=z[j];
            z[i]=a[i]+max;
        }
        max=0;
        for(i=n-d; i<n; i++)
            if(z[i]>max)
                max=z[i];
        cout<<max;
  
        return 0;
}
Dekio
Фрилансер
Эксперт C++
 Аватар для Dekio
5816 / 1214 / 214
Регистрация: 23.11.2010
Сообщений: 3,378
Записей в блоге: 1
02.11.2011, 00:13     Последовательность #5
Цитата Сообщение от valeriikozlov Посмотреть сообщение
int a[1000]; int z[1000];
Зачем выделять столько не нужной памяти, если даже 1/50 этой памяти врятли будет использована?
Не проще использовать динамические массивы?
valeriikozlov
Эксперт C++
 Аватар для valeriikozlov
4660 / 2486 / 321
Регистрация: 18.08.2009
Сообщений: 4,550
02.11.2011, 06:38     Последовательность #6
Цитата Сообщение от Dekio Посмотреть сообщение
Зачем выделять столько не нужной памяти, если даже 1/50 этой памяти врятли будет использована?
Не совсем так. По условию:
Цитата Сообщение от Montanaa Посмотреть сообщение
2 <= N <= 1000;
А значит есть тесты в которых память будет использована по полной. И что самое главное не будет превышен лимит по памяти, данный в условии.

Цитата Сообщение от Dekio Посмотреть сообщение
Не проще использовать динамические массивы?
Это уже личное дело каждого. В принципе можно.
Но есть и отрицательные стороны динамических массивов:
- в случае использования динамических массивов - время выполнения программы увеличивается (по сравнению с использованием статических массивов). А в задаче стоит ограничение по времени.
Но еще раз повторю - это личное дело каждого, можно и так, можно и с использованием динамических массивов.
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
03.11.2011, 13:00     Последовательность
Еще ссылки по теме:

C++ Дана последовательность, элементы которой есть целые двузначные числа. Упорядочить последовательность по убыванию произведений цифр
Массив: Вставить в последовательность действительное число b так, чтобы последовательность осталась неубывающей. C++
Если последовательность отсортирована по возрастанию, оставить ее без изменения. Иначе получить иную последовательность C++

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

Или воспользуйтесь поиском по форуму:
Mr.X
Эксперт С++
 Аватар для Mr.X
2807 / 1583 / 248
Регистрация: 03.05.2010
Сообщений: 3,686
03.11.2011, 13:00     Последовательность #7
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
/////////////////////////////////////////////////////////////////////////////////////////
//Дана последовательность N целых чисел A[1], A[2], ..., A[N]. 
//Подпоследовательность называется красивой, если любые два ее элемента имеют 
//разность индексов в первоначальной последовательности не менее D.
//Формально, пусть A[i1], A[i2], ..., A[ik] - подпоследовательность длины k, 
//тогда она будет красивой, если i2 - i1 >= D и i3 - i2 >= D и ... и ik - ik-1 >= D.
//Найдите максимальную сумму элементов среди всех красивых подпоследовательностей 
//заданной последовательности.
//
//Входные данные
//В первой строке входного файла заданы натуральные числа N и D (2 <= N <= 1000; 1 <= D <= N - 1). 
//В следующей строке находятся N целых чисел A[i] (1 <= A[i] <= 10000).
//
//Выходные данные
//В результирующем файле должно находится искомое целое число.
//
//Пример
//
//Ввод
//5 3
//4 2 5 1 7
//
//Вывод
//11
/////////////////////////////////////////////////////////////////////////////////////////
#include <iostream>
#include <vector>
/////////////////////////////////////////////////////////////////////////////////////////
typedef std::vector<int>  T_array;
/////////////////////////////////////////////////////////////////////////////////////////
int   get_maximum_total_of_beautiful_subsequence
    (
        T_array  arr,
        int      d
    )
{
    int  res      = 0;
    int  cur_max  = 0;    
    for(size_t  i = d; i < arr.size(); ++i)
    {
        if(arr[i - d] > cur_max)
        {
            cur_max = arr[i - d];
        }
        arr[i] += cur_max;
        if(arr[i] > res)
        {
            res = arr[i];
        }
    }
    return  res;
}
/////////////////////////////////////////////////////////////////////////////////////////
int main()
{
    std::locale::global(std::locale(""));   
    std::cout << "Введите минимальную разность индексов:"
              << '\t';
    int  d = 0; 
    std::cin >> d;
 
    std::cout << "Введите длину последовательности:"
              << '\t';
    int  n = 0; 
    std::cin >> n;
 
    std::cout << std::endl
              << "Введите "
              << n
              << " натуральных чисел:"
              << std::endl;
 
    T_array  arr(n);
    for(int  i = 0; i < n; ++i)
    {
        std::cout << "#"
                  << i + 1
                  << ":"
                  << '\t';
        
        std::cin >> arr[i];
    }
 
    std::cout << std::endl
              << "Максимальная сумма элементов подпоследовательности с разностью индесов"
              << std::endl
              << "соседних элементов не меньше "
              << d
              << " равна "
              << get_maximum_total_of_beautiful_subsequence(arr, d)
              << "."
              << std::endl
              << std::endl;
}
Yandex
Объявления
03.11.2011, 13:00     Последовательность
Ответ Создать тему
Опции темы

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