C++ Динамическое программирование. Где недочет?

[UaKot]

Сообщение от Smogg

На таком входе:
6
1 2 7 14 15 16

отвечает 8.

Здесь мерещится мне какая-то фигня с непроверкой граничных условий.

Хотя чем дальше, тем меньше я понимаю, что в итоге из этого исходника у меня накомпилялось и как вообще решать задачу кроме тупого перебора..

Так все правильно же. 8.
1-2-7 14-15-16
(2-1) + (7-2) + (15-14) + (16 - 15) = 8
как раз 8.. и меньше нельзя.

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

[BDA]

На обоих сайтах ОК.

#include <fstream>
#include <algorithm>

int 
main()
{
    int N;
    std::ifstream fin("input.txt");
    std::ofstream fout("output.txt");
    fin >> N;
    int *a = new int[N];
    for (int i = 0; i < N; i++)
        fin >> a[i];
    std::sort(a, a + N);
    if (N == 2 || N == 3) {
        fout << a[N - 1] - a[0];
    } else {
        int *b = new int[N - 1];
        b[0] = a[1] - a[0];
        b[1] = a[2] - a[0];
        for (int j = 2; j < N - 1; ++j)
            b[j] = std::min(b[j - 1], b[j - 2]) + a[j + 1] - a[j];
        fout << b[N - 2];
        delete []b;
    }
    delete []a;
}

Формула подсмотрена на informatics.

[UaKot]

Сообщение от BDA

На обоих сайтах ОК.

#include <fstream>
#include <algorithm>

int 
main()
{
    int N;
    std::ifstream fin("input.txt");
    std::ofstream fout("output.txt");
    fin >> N;
    int *a = new int[N];
    for (int i = 0; i < N; i++)
        fin >> a[i];
    std::sort(a, a + N);
    if (N == 2 || N == 3) {
        fout << a[N - 1] - a[0];
    } else {
        int *b = new int[N - 1];
        b[0] = a[1] - a[0];
        b[1] = a[2] - a[0];
        for (int j = 2; j < N - 1; ++j)
            b[j] = std::min(b[j - 1], b[j - 2]) + a[j + 1] - a[j];
        fout << b[N - 2];
        delete []b;
    }
    delete []a;
}

Формула подсмотрена на informatics.

Спасибо, но я нашел свою ошибку При N == 3 or N == 4 у меня вывод был в консоль, я забывал переделать в файл ) А на другом сайте и в консоль, и в файл можно, вот он все и проходил там.

P.S. мой алгоритм быстрее этого :Р

[BDA]

Сообщение от UaKot

Спасибо, но я нашел свою ошибку При N == 3 or N == 4 у меня вывод был в консоль, я забывал переделать в файл ) А на другом сайте и в консоль, и в файл можно, вот он все и проходил там.

P.S. мой алгоритм быстрее этого :Р

Хорошо, что нашли.
Разницы в скорости почти нет:
Ваш:

1 Accepted 0,05 60 Кб
2 Accepted 0,008 60 Кб
3 Accepted 0,008 60 Кб
4 Accepted 0,01 60 Кб
5 Accepted 0,008 60 Кб
6 Accepted 0,008 60 Кб
7 Accepted 0,008 60 Кб
8 Accepted 0,008 60 Кб
9 Accepted 0,008 60 Кб
10 Accepted 0,01 60 Кб
11 Accepted 0,008 60 Кб
12 Accepted 0,01 60 Кб
13 Accepted 0,008 60 Кб
14 Accepted 0,008 60 Кб
15 Accepted 0,009 60 Кб
16 Accepted 0,01 60 Кб

"Мой":

1 Accepted 0,042 60 Кб
2 Accepted 0,008 60 Кб
3 Accepted 0,008 60 Кб
4 Accepted 0,008 60 Кб
5 Accepted 0,008 60 Кб
6 Accepted 0,008 60 Кб
7 Accepted 0,012 60 Кб
8 Accepted 0,008 60 Кб
9 Accepted 0,007 60 Кб
10 Accepted 0,008 60 Кб
11 Accepted 0,008 60 Кб
12 Accepted 0,008 60 Кб
13 Accepted 0,01 60 Кб
14 Accepted 0,009 60 Кб
15 Accepted 0,008 60 Кб
16 Accepted 0,009 60 Кб

При отказе от динамического выделения памяти:

1 Accepted 0,035 60 Кб
2 Accepted 0,009 60 Кб
3 Accepted 0,008 60 Кб
4 Accepted 0,008 60 Кб
5 Accepted 0,01 60 Кб
6 Accepted 0,008 60 Кб
7 Accepted 0,008 60 Кб
8 Accepted 0,008 60 Кб
9 Accepted 0,008 60 Кб
10 Accepted 0,008 60 Кб
11 Accepted 0,008 60 Кб
12 Accepted 0,008 60 Кб
13 Accepted 0,008 60 Кб
14 Accepted 0,009 60 Кб
15 Accepted 0,008 60 Кб
16 Accepted 0,008 60 Кб

#include <fstream>
#include <algorithm>

int 
main()
{
    int N, a[100], b[100];
    std::ifstream fin("input.txt");
    std::ofstream fout("output.txt");
    fin >> N;
    for (int i = 0; i < N; i++)
        fin >> a[i];
    std::sort(a, a + N);
    if (N == 2 || N == 3) {
        fout << a[N - 1] - a[0];
    } else {
        b[0] = a[1] - a[0];
        b[1] = a[2] - a[0];
        for (int j = 2; j < N - 1; ++j)
            b[j] = std::min(b[j - 1], b[j - 2]) + a[j + 1] - a[j];
        fout << b[N - 2];
    }
}

[Smogg]

Сообщение от UaKot

Спасибо, но я нашел свою ошибку При N == 3 or N == 4 у меня вывод был в консоль, я забывал переделать в файл )

Алгоритм верный. Значит, все таки молодец!

Опечатки - всего лишь опечатки.
Если использовать #ifdef _DEBUG#else...#endif, то код сразу перестает быть лаконичным и красивым.