Вырезать палку, чтобы минимизировать затраты

Ответ 1

Еще одно решение DP:

Пусть COST (a, b) - лучшая стоимость резки сегмента между a -той и b-й точкой разреза. Ясно, что COST (a, a) и COST (a, a + 1) равны нулю. Мы можем вычислить наилучшее значение COST (a, b) как минимум разрезов через все средние точки a + 1... b-1 плюс собственную длину сегмента. Таким образом, мы можем заполнить диагональ треугольной таблицы по диагонали и найти конечный результат как COST (начало, конец) с временной сложностью O (N ^ 3) и O (N ^ 2) space

Код Delphi (выходы Cost 20 Sequence 4 2 7)

var
  Cuts: TArray<Integer>;
  Cost: array of array of Integer;
  CutSequence: array of array of String;
  N, row, col, leftpos, rightpos, cutpos, Sum: Integer;
begin
  Cuts := TArray<Integer>.Create(0, 2, 4, 7, 10); // start, cuts, end points
  N := Length(Cuts);
  SetLength(Cost, N, N);  //zero-initialized 2D array
  SetLength(CutSequence, N, N);  //zero-initialized 2D array

  for rightpos := 2 to N - 1 do
    for leftpos := rightpos - 2 downto 0 do begin //walk along the diagonals
                                                  //using previously computed results
      //find the best (mincost) cut
      Cost[leftpos, rightpos] := MaxInt; //big value
      for cutpos := leftpos + 1 to rightpos - 1 do begin
        Sum := Cost[leftpos, cutpos] + Cost[cutpos, rightpos];
        if Sum < Cost[leftpos, rightpos] then begin
          Cost[leftpos, rightpos] := Sum;
          //write down best sequence
          CutSequence[leftpos, rightpos] := Format('%d %s %s', [Cuts[CutPos],
            CutSequence[leftpos, cutpos], CutSequence[cutpos, rightpos]]);
        end;
      end;

      //add own length
      Cost[leftpos, rightpos] :=
        Cost[leftpos, rightpos] + Cuts[rightpos] - Cuts[leftpos];
    end;

  //show the best result
  Caption := Format('Cost %d  Sequence %s',[Cost[0, N-1], CutSequence[0, N-1]]);

Ответ 2

На самом деле это проблема судьи UVa Online. http://uva.onlinejudge.org/index.php?option=com_onlinejudge&Itemid=8&page=show_problem&problem=944

В этой задаче L < 1000 и n < 50.

Как я уже упоминал в комментариях, если вы заметили тогда для каждого разреза, возможные длины палки, при которых разрез может быть сделан = n.

Общее возможное remaining lengths должно быть конечным, и для каждой оставшейся длины число sets of cuts remaining также будет конечным. Таким образом, вы можете построить DP на оставшихся длинах.

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

Что-то вроде:

DP[k][SetOfCutsRemaining] = k + Min( DP[m1][SetOfCutsRemaining till c1] 
                                 + DP[k-m1][SetOfCutsremaining from c1], 
                                 DP[m2][SetOfCutsRemaining till c2] 
                                 + DP[k-m2][SetOfCutsremaining from c2],... )
                           where mi are the lengths remaining if we make a cut at ci

Вам нужно будет сделать это до DP[L][InitialSetOfCuts].

В примере проблемы L = 10, ci = 2, 4, 7

Остальные длины и их соответствующие сокращения остаются следующими. Обратите внимание, что количество комбинаций должно быть C (n + 2,2) = (n + 2) (n + 1)/2 = 10 в этом случае

2 {} (2 times, 0-2 and 2-4)
3 {} (2 times, 4-7 and 7-10)
4 {c1}
5 {c2}
6 {c3}
7 {c1, c2}
8 {c2, c3}
10 {c1, c2, c3}

DP[2][{}] = 0 (No cut remaining)
DP[3][{}] = 0 (No cut remaining)
DP[4][{c1}] = 4 (1 cut remaining)
DP[5][{c2}] = 5 (1 cut remaining)
DP[6][{c3}] = 6 (1 cut remaining)
DP[7][{c1,c2}] = 7 + Min( DP[2]{} + DP[5][{c2}], DP[3]{} + DP[4][{c1}] )
               = 7 + Min( 5, 4 ) = 11.
DP[8][{c2,c3}] = 8 + Min( DP[2]{} + DP[6][{c3}], DP[3]{} + DP[5][{c2}] )
               = 8 + Min( 6, 5 ) = 13.
DP[10][{c1,c2,c3}] = 10 + Min( DP[2]{} + DP[8][{c2,c3}], DP[4]{c1} + DP[6][{c3},
                                DP[7][{c1,c2}] + DP[3]{} )
               = 10 + Min( 13, 10, 11 ) = 20.

Ответ 3

Во-первых, предположим, что у нас есть массив пошагового упорядочения, поэтому в примере OP это будет {2,4,7}

Сначала мы имеем палку с длиной от 0 до n, поэтому мы вызываем функцию

int cal(int start, int end , int [] cuts)

с start = 0 и end = n.

Для каждой точки резания, которая больше, чем начало и меньше конца, мы имеем формулу

int result = 1000000;
for(int i = 0; i < cuts.length; i++){
   if(cuts[i]> start && cuts[i]<end){
         int val = (end - start) + cal(start, cuts[i], cuts) + cal(cuts[i],end , cuts); 
         result = min(val, result);
   } 
}

а таблица DP может быть просто

dp[start][end]

Итак, все решение будет:

int cal(int start, int end, int[]cuts){
    if(dp[start][end]!= -1){//Some initializations need to be done
        return dp[start][end];
    }
    int result = 1000000;
    for(int i = 0; i < cuts.length; i++){
       if(cuts[i]> start && cuts[i]<end){
         int val = (end - start + 1) + cal(start, cuts[i], cuts) + cal(cuts[i],end , cuts); 
         result = min(val, result);
       } 
    }
    return dp[start][end] = result;
}

Чтобы еще больше расширить пространство, мы можем ссылаться на каждую позицию резки как свой индекс в массиве cuts.

Добавлены начальные и конечные точки массивов разрезов, у нас есть следующие массивы

{0,2,4,7,10}

Обращаясь к исходной позиции как индекс 0, оканчиваемся как индекс 4, мы можем уменьшить пространство массива dp от dp [10] [10] до dp [5] [5]

Ответ 4

Извините, я могу гудеть как холодильник в любое время, но говорить в математике - это большая проблема. Я, вероятно, мог бы формализовать алгоритм жизни меня, но до тех пор, пока полиция кармы оставляет меня в покое, я не буду.

Вот мое решение (в JavaScript).

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

Похоже, что количество исследованных разрезов для n разрезов равно 3 ^^ n (я его измерил). Я подозреваю, что для этого есть тривиальное объяснение, но попытка найти это вызывает у меня головокружение, поэтому...

Я использую формат, предложенный в другом комментарии, то есть самый левый и самый правый элементы массива представляют собой концы текущего бита палки.
Например, [0,2,4,7,10] означает "разрезы в положениях 2, 4 и 7 в палочке в диапазоне от 0 до 10".

function try_cut_raw (list)
{
    // terminal ends
    if (list.length == 2) return 0;
    if (list.length == 3) return list[2]-list[0];

    // left and right split
    var cost_min = 1e6;
    for (var i = 1 ; i != list.length-1 ; i++)
    {
        var cost = try_cut_raw (list.slice (0, i+1))
                 + try_cut_raw (list.slice (i, list.length));
        if (cost < cost_min) cost_min = cost;
    }
    return cost_min+list[list.length-1]-list[0];
}

Более утонченный, возвращая полуупорядоченную последовательность разрезов, применяемых для достижения результата.

function try_cut (list)
{
    // terminal ends
    if (list.length == 2) return { cost: 0, seq:[] };
    if (list.length == 3) return { cost: list[2]-list[0], seq:[list[1]] };

    // left and right split, retaining best value
    var i_min;
    var cost_min = 1e6;
    var seq_min;
    for (var i = 1 ; i != list.length-1 ; i++)
    {
        var cl = try_cut (list.slice (0, i+1));
        var cr = try_cut (list.slice (i, list.length));

        var cost = cl.cost+cr.cost;
        if (cost < cost_min)
        {
            cost_min = cost;
            // store cut order associated with best result
            seq_min  = [list[i]].concat (cl.seq).concat(cr.seq);
        }
    }
    return { cost: cost_min+list[list.length-1]-list[0], seq: seq_min }
}

Тестовый пример с вводом OP и оба примера с начальной страницы запроса

function cut (list)
{
var cut = try_cut (list);
var cut_raw = try_cut_raw (list);
console.log ("["+list+"] -> "+cut.seq+" cost "+cut.cost+"/"+cut_raw);
}

cut ([0,2,4,7,10]);
cut ([0,25,50,75,100]);
cut ([0,4,5,7,8,10]);

Выход

[0,2,4,7,10] -> 4,2,7 cost 20/20
[0,25,50,75,100] -> 50,25,75 cost 200/200
[0,4,5,7,8,10] -> 4,7,5,8 cost 22/22

Ответ 5

Я уважаю все вышеприведенное решение. Вот мое решение для этой проблемы в Java.

Это может быть полезно для кого-то.

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

public class CutTheSticks2 {
    public static void main(String s[]) throws NumberFormatException, IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));

        short N = Short.parseShort(br.readLine());
        short[] A = new short[N];
        N = 0;
        for (String str : br.readLine().split(" ")) {
            A[N++] = Short.parseShort(str);
        }

        Arrays.sort(A);

        StringBuffer sb = new StringBuffer();
        System.out.println(N);
        for (int i = 1; i < N; i++) {
            if (A[i - 1] != A[i]) {
                sb.append((N - i) + "\n");
            }
        }

        // OUTPUT
        System.out.print(sb);
    }
}