Вот черновик решения проблемы с использованием грубой силы в предположении, что оптимальное решение для n баров может быть найдено в сетке, имеющей только n + 1 столбцов (Это предположение кажется неверным, по крайней мере, для n>= 8. Изменяя параметры, можно расширить поиск, но это еще больше замедлит поиск).
Алгоритм имеет экспоненциальную сложность и даст результаты только в течение полезного времени для очень низких чисел. Как я уже говорил в комментариях, этот подход может быть несколько улучшен за счет сокращения пространства поиска, позволяющего использовать только комбинации тактов, имеющих форму песочных часов (длинные бары снаружи, короткие бары внутри).
Может быть все же выгодно найтирешение по построению, где ищется оптимальное решение для n + 1 баров путем расширения оптимального решения для n баров путем добавления еще одного бара выше или ниже. Даже если это не оптимально, это может обеспечить полезную верхнюю границу для оптимального решения.
public class BarConnection {
static class Bar {
int start, end;
private final int maxlength, minlength;
Bar(int maxlength, int minlength) {
this.maxlength = maxlength;
this.minlength = minlength;
reset();
}
public boolean next() {
start++;
if (start > 0) {
return reset((end - start) + 2);
}
end++;
return true;
}
public void reset() {
reset(minlength);
}
public boolean reset(int length) {
if (length > maxlength) {
return false;
}
start = -length;
end = 0;
return true;
}
}
static class Solution {
private Bar[] bars;
private int globalmin, globalmax, cost;
Solution(int n) {
bars = new Bar[n];
for (int i = 0; i < n; i++) {
bars[i] = new Bar(/* maxlength */ n, /* minlength */ 1);
}
}
private boolean connect(final int maxcost) {
cost = Integer.MAX_VALUE;
int sumcost = 0;
for (int i = 0; i < (bars.length - 1); i++) {
for (int j = i + 1; j < bars.length; j++) {
final int pairCost = minCostBetween(i, j);
if (pairCost == 0) {
continue;
}
sumcost += pairCost;
if (sumcost > maxcost) {
return false;
}
}
}
cost = sumcost;
return true;
}
boolean nextSolution(final int maxcost) {
while (true) {
while (bars[0].next()) {
if (connect(maxcost)) {
return true;
}
}
bars[0].reset();
for (int i = 1; i < bars.length; i++) {
if (bars[i].next()) {
break;
}
if (i == bars.length - 1) {
return false;
}
bars[i].reset();
}
if (connect(maxcost)) {
return true;
}
}
}
private int minCostBetween(final int i, final int j) {
int minConnectionCost = -1;
for (int k = Math.max(bars[i].start, bars[j].start); k <=
Math.min(bars[i].end, bars[j].end); k++) {
// calculate cost for connecting at column k
int newcost = 0;
for (int l = i + 1; l < j; l++) {
final Bar midbar = bars[l];
if ((k >= midbar.start) && (k <= midbar.end)) {
newcost++;
if ((minConnectionCost >= 0) && (newcost >=
minConnectionCost)) {
break;
}
}
}
if ((minConnectionCost < 0) || (newcost < minConnectionCost)) {
minConnectionCost = newcost;
if (newcost == 0) {
break;
}
}
}
return minConnectionCost;
}
}
public static void main(String[] args) {
int n = 6
final Solution searchState = new Solution(n);
int minCost = Integer.MAX_VALUE;
while(true) {
if (!searchState.nextSolution(minCost - 1)) {
break;
}
minCost = searchState.cost, minCost;
if (minCost == 0) {
break;
}
}
System.out.println("n=" + n + ", p=" + minCost);
}
}