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

#cpp #алгоритм

  Имеем доску, в которую на определенном расстоянии друг от друга вбиты гвозди. Любые
два гвоздя можно соединить веревкой. Надо соединить веревкой некоторые пары гвоздей
так, чтобы к каждому гвоздю была привязана веревка, а расстояние между гвоздями было
минимальным.
  
  Вводные данные: дано целое число 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

Ответы
Ответ 1

Ясно, что соединять веревкой имеет смысл только соседние гвозди (после сортировки
расположения гвоздей).

На самом деле - ну их нафиг, эти паросочетания (см. ниже). Прав @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


Ответ 2

Решение перебором: 

рассмотрим два случая - 1. в начале находится один отрезок и пропуск, 2. в начале
находятся два отрезка и пропуск. Потом для каждого из этих случаев рекурсивно рассматриваем
оставшиеся гвозди.

Естественно, гвозди считаем упорядоченными на числовой прямой.

Равшан: "Писка: Фости, десять клох смен, ..."


Ответ 3

Если я не ошибаюсь, и правильно все понял. То это задача на графах о поиске остова
минимального веса графа. Решить можно либо алгоритмом Краскала либо алгоритмом Дейкстры. 

Краскала (http://e-maxx.ru/algo/mst_kruskal_with_dsu)

Дейкстры (https://ru.wikibooks.org/wiki/%D0%A0%D0%B5%D0%B0%D0%BB%D0%B8%D0%B7%D0%B0%D1%86%D0%B8%D0%B8_%D0%B0%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC%D0%BE%D0%B2/%D0%90%D0%BB%D0%B3%D0%BE%D1%80%D0%B8%D1%82%D0%BC_%D0%94%D0%B5%D0%B9%D0%BA%D1%81%D1%82%D1%80%D1%8B)

Вот пример Краскала:

void kruskal()
{
    //  суммарный вес минимального остова
    int sum = 0;
    vector> mst;
    mst.clear();
    //  для корректной работы алгоритма все ребра графа должны быть отсортированы по весу
    sort(graph.begin(), graph.end());
    vector tree_id(N);
    for (int i = 0; i < N; i++)
        tree_id[i] = i;
    //  обход списка ребер методом  раскала
    for (int i = 0; i < M; i++)
    {
        int a = graph[i].start, b = graph[i].fin, w = graph[i].weight;
        if (tree_id[a] != tree_id[b])
        {
            sum += w;
            mst.push_back(make_pair(a, b));
            int old_id = tree_id[b], new_id = tree_id[a];
            for (int j = 0; j < N; j++)
                if (tree_id[j] == old_id)
                    tree_id[j] = new_id;
        }
    }
    //  вывод минимального остова
    for (int i = 0; i < mst.size(); i++)
        printf("%d -> %d\n", mst[i].first, mst[i].second);
    printf("MST weight = %d\n", sum);
    mst.clear();
    tree_id.clear();
}