Задача с доской

Имеем доску, в которую на определенном расстоянии друг от друга вбиты гвозди. Любые два гвоздя можно соединить веревкой. Надо соединить веревкой некоторые пары гвоздей так, чтобы к каждому гвоздю была привязана веревка, а расстояние между гвоздями было минимальным. Вводные данные: дано целое число N — количество гвоздей (2 ≤ N ≤ 100). На другой строчке даны N чисел — координаты гвоздей (разные, неотрицательные числа, которые не превышают 10000). Вывод: Вывести минимально возможную длину всех веревок. Примеры Ввода/Вывода:
+------------------+-------------------+ | стандартный ввод | стандартный вывод | +------------------+-------------------+ | 6 | 5 | | 3 4 12 6 14 13 | | +------------------+-------------------+ | 7 | 5 | | 3 2 1 4 5 7 9 | | +------------------+-------------------+
Мой код:
#include #include #include
using namespace std;
int n, sk[10000], min[10000], not[10000], tot; int ats=0;
int main() {
cin >> n; for(int i=0;i> sk[i]; } for(int a=0;a } else { min[y]=abs(sk[y]-sk[e]); tot=e; } } } } for(int l=0;l

Ответ

Ясно, что соединять веревкой имеет смысл только соседние гвозди (после сортировки расположения гвоздей).
На самом деле - ну их нафиг, эти паросочетания (см. ниже). Прав @Igor - рекурсия (с мемоизацией) тут будет в самый раз.
Ясно, что первый и последний промежуток между гвоздями надо связывать обязательно. Если второй промежуток не связывать, то третий - надо связывать обязательно. Если второй промежуток связывать, то третий - нельзя связывать, а четвертый - надо связывать обязательно.
Получаем схему рекурсивного перебора:
связывать - не связывать - (рекурсивный вызов) связывать - связывать - не связывать - (рекурсивный вызов)
(Опять же - это полностью соответствует ответу @Igor.)
На С++
#include #include #include #include #include #include
using Weight = unsigned; using Weights = std::vector;
Weight min_sum(const Weights &weights, size_t i = 0) { assert(i < weights.size()); size_t n = weights.size() - i;
if (n == 1) return weights[i]; else if (n == 2) return weights[i] + weights[i + 1]; else if (n == 3) return weights[i] + weights[i + 2]; else return std::min( weights[i] + min_sum(weights, i + 2), weights[i] + weights[i + 1] + min_sum(weights, i + 3)); }
int main() { std::vector nails; std::copy(std::istream_iterator(std::cin), std::istream_iterator(), std::back_inserter(nails)); std::sort(nails.begin(), nails.end()); std::copy(nails.begin(), nails.end(), std::ostream_iterator(std::cout, " ")); std::cout << std::endl;
Weights weights; std::adjacent_difference(nails.begin(), nails.end(), std::back_inserter(weights)); weights.erase(weights.begin()); std::copy(weights.begin(), weights.end(), std::ostream_iterator(std::cout, " ")); std::cout << std::endl;
std::cout << min_sum(weights) << std::endl; }
http://coliru.stacked-crooked.com/a/13244f823d44f93d
Имеет смысл добавить мемоизацию по i, ибо возникновение одинаковых подзадач - возможно.

Непереборный подход:
Задача является задачей поиска реберного покрытия минимального веса в "зигзагообразном" двудольном графе (одна доля - четные гвозди, другая - нечетные, вес ребра W(u,v) равен расстоянию между гвоздями). Возможно (и даже скорее всего), это чересчур общий подход, т.е. "стрельба из пушки по воробъям", ибо граф имеет очень простую структуру, но пока закроем на это глаза.
Далее следуем предложенному самим Дэвидом Эппстейном вот здесь подходу. Ясно, что комбинации из трех последовательных ребер не имеют смысла - среднее ребро в такой комбинации является лишним. Тогда любое решение можно представить в виде некоего паросочетания M в исходном графе, плюс возможно несколько дополнительных ребер, предназначенных для присоединения непокрытых паросочетанием M вершин. Ясно, что непокрытые паросочетанием M вершины надо присоединять к M через ребра минимального веса, выходящие из таких вершин.
Пусть C(v) - это веc самого короткого ребра, выходящего из вершины v. Тогда вес решения, определяемого паросочетанием M, можно записать как
Σ C(v) - Σ С(u) + C(v) − W(u,v) | | по всем v по всем (u,v) из M
Первая Σ не зависит от M. Поэтому, чтобы минимизировать вес решения, нам надо максимизировать вторую Σ. А это - задача о паросочетании максимального веса в том же самом двудольном графе, но с весами ребер
W'(u, v) = С(u) + C(v) − W(u,v)
Задача, возможно, упрощается "зигзагообразностью" двудольного графа. Задача, возможно, усложняется наличием отрицательных весов.
Осталось только решить задачу о паросочетании максимального веса в таком графе ))) (Хотя, как справедливо заметил в комментариях @Fat-Zer, задача интуитивно не выглядит более простой, чем исходная)

Например
1.
Гвозди 3 4 6 12 13 14 W 1 2 6 1 1 С(v) 1 1 2 1 1 1 W' 1 1 -3 1 1
Максимальное паросочетание M (одно из возможных): 3-4, 12-13 Добавляем непокрытые вершины ребрами минимальной длины:
3-4-6 12-13-14
Вес: 5
2.
Гвозди 1 2 3 4 5 7 9 W 1 1 1 1 2 2 С(v) 1 1 1 1 1 2 2 W' 1 1 1 1 1 2
Максимальное паросочетание M (одно из возможных): 2-3, 4-5, 7-9 Добавляем непокрытые вершины ребрами минимальной длины:
1-2-3 4-5 7-9
Вес: 5
3.
Гвозди 1 2 5 9 11 12 W 1 3 4 2 1 С(v) 1 1 3 2 1 1 W' 1 1 1 1 1
Максимальное паросочетание M: 1-2, 5-9, 11-12 Добавлять нечего.
Вес: 6