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

[UaKot]

На одном сайте задача прошла все тесты, но на другом валится из-за неправильного ответа... значит где-то ошибка... Где?

На прямой дощечке вбиты гвоздики. Любые два гвоздика можно соединить ниточкой. Требуется соединить некоторые пары гвоздиков ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка, а суммарная длина всех ниточек была минимальна.

Входные данные

В первой строке входного файла INPUT.TXT записано число N - количество гвоздиков (2 <= N <= 100). В следующей строке записано N чисел - координаты всех гвоздиков (неотрицательные целые числа, не превосходящие 10000).

Выходные данные

В выходной файл OUTPUT.TXT нужно вывести единственное число - минимальную суммарную длину всех ниточек.

Вход
6
3 4 12 6 14 13

Выход
5

Само решение:

#include <iostream>
#include <fstream>

using namespace std;

int a[100] = {0};

void quickSort(int l, int r)
{
    int x = a[l + (r - l) / 2];
    int i = l;
    int j = r;
    while(i <= j)
    {
        while(a[i] < x) i++;
        while(a[j] > x) j--;
        if(i <= j)
        {
            swap(a[i], a[j]);
            i++;
            j--;
        }
    }
    if (i<r)
                quickSort(i, r);
    
    if (l<j)    
        quickSort(l, j);    
}

int main(){
	int N;
	ifstream fin("inp");
	// ofstream fout("output.txt");
	fin >> N;
	for (int i = 0; i < N; i++)
		fin >> a[i];
	fin.close();
	quickSort(0, N-1);
	if (N == 2){
		cout << a[1] - a[0];
		return 0;
	}
	if (N == 3){
		cout << a[2] - a[0];
		return 0;
	}
	int F[101] = {0};
	int i = 5;
	F[3] = 99999; // Заведомо самое большое...
	F[4] = a[1]-a[0] + a[N-1] - a[N-2]; // Для 4 гвоздиков ответ известен.. Поиск далее.
	while (i <= N){
		F[i] = min(min(F[i-1] + a[i-2] - a[i-3], F[i-1] + a[i-3] - a[i-4]),F[i-2] + a[i-3] - a[i-4]); // По-моему очень громоздкая формула суммы...
		i++;
	}
	cout << F[N];
	return 0;
}

inp я заменяю на input.txt и cout на fout перед тестом) И комментарий с ofstream тоже снимаю)

[Smogg]

А разве не будет минимальной длиной ниточек просто длина целой ниточки, протянутой от первого гвоздика до последнего? Т.е. координата самого дальнего гвоздика минус координата ближнего?

Вот если бы координаты давались двухмерные (трех-, четырех-)...

[revizor]

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

А разве не будет минимальной длиной ниточек просто длина целой ниточки, протянутой от первого гвоздика до последнего?

Это было бы правильно если к каждому гвоздику шла только одна нить. а здесь по другому

"требуется соединить некоторые пары гвоздиков ниточками так, чтобы к каждому гвоздику была привязана хотя бы одна ниточка"
т.е. от каждого гвоздика может идти 2, 3, 4 нити.

[revizor]

Хотя не знаю. может я неправильно понял эту задачу

[UaKot]

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

Хотя не знаю. может я неправильно понял эту задачу

Все правильно. Я же тест привел. Только больше 2х ниточек от одного гвоздика смысла не имеет проводить) Нужно соединять только соседние так, что бы сумма длин отрезков ниточки была минимальной.

Вот еще правильные тесты:

Вход
29
593 716 845 603 858 545 848 424 624 646 385 438 298 892 57 964 273 384 478 792 813 529 480 569 393 926 837 72 338
Выход
340

Вход
10
682 2517 2478 2816 4980 5839 6414 7667 8802 8995
Выход
4400

Явно, не от от первого, до последнего. И все эти тесты у меня алгоритм проходит, но на проверке какой-то валит. Или не один. На другом сайте, с другими тестами проходит все на 100%.

Ну или самое элементарное
Вход
6
1 2 3 4 5 6
Выход
3

Потому что 1-2 3-4 5-6 можно соединить, и длина - 3.

[revizor]

а откуда эта задача? с какого сайта?
UaKot, напиши пожалуста. мне интересно посмотреть.

[UaKot]

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

а откуда эта задача? с какого сайта?
UaKot, напиши пожалуста. мне интересно посмотреть.

http://acmp.ru/index.asp?main=task&id_task=121 на этом сайте тест не проходит
http://informatics.mccme.ru/moodle/m...ew.php?id=4958 на этом проходит все тесты

[BDA]

Например, есть на ACMP.
ПС Опоздал

[revizor]

BDA, спасибо!

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

[Smogg]

удалено, ибо ошибочно