Problem z zrozumieniem treści

Jak co roku w Bajtocji zima zaskoczyła Bajtockie Koleje Państwowe BKP. Duży mróz powoduje, że szyny pękają i istnieje konieczność ciągłego ich naprawiania. Zakładając, że szyna pękła w N miejscach, gdzie 1≤N≤1000, zaś poszczególne kawałki mają długość 0<L[n]≤10 metrów, gdzie 1≤n≤N, koszt połączenia szyny pomiędzy odcinkami i oraz j, gdzie 1≤i<j≤N, można wyznaczyć obliczając koszt połączenia odcinków od i do k oraz odcinków od k+1 do j, gdzie 1≤i≤k<j≤N oraz dodając do niego sumę L[i]+L[k]+L[j]. Wartość kosztu naprawy całej szyny to koszt połączenia odcinków od 1 do N. Koszt ten zależy od kolejności łączenia odcinków. Napisać program, który wyznaczy minimalny koszt naprawy szyny oraz kolejność łączenia odcinków przy zadanym N oraz zadanych długościach odcinków L[n]. Zadanie należy rozwiązać rekurencyjnie oraz z wykorzystaniem programowania dynamicznego sprawdzając ile czasu potrzeba na realizację każdego z podejść.
Przykład:
Dla N=5 pęknięć i przy odcinkach równych L[1]=4, L[2]=6, L[3]=10, L[4]=9 oraz L[5]=2 optymalny sposób łączenia polega w na łączeniu odcinków po kolei od końca. Koszt takiego łączenia to 66. Przykładowo, przy łączeniu odcinków po kolei od początku koszt ten wynosi 80.

czy to ma prawo być rozwiązaniem zadania??

int N;
    cin>>N;
    int *L=new int[N];
    for(int i=0;i<N;i++)
        cin>>L[i];
    int suma=0;
    if(N>=3)
        for(int i=0;i<=N-3;i++)
        {
            suma+=L[i]+L[i+1]+L[i+2];
        }
    else
        if(N==2)
            suma=L[0]+L[1];
        if(n==1)
            suma=L[0];
    cout<<suma;
    delete [] L;

Chyba nie rozumiem treści.. i w ogóle nie potrafię dojść w jaki sposób wyszło im 80.. czy liczę od przodu czy od tyłu zawsze jest 66.. i jestem skłonny twierdzić, że te dane to podpucha a ja źle to licze;)

Ja tez nie lapie(66 w obie strony mi wychodzi). Dodam jeszcze, że jak odcinków jest 5 to przecież pęknięć musi być 4 ?! Nie napisali żeby łączyć ostatni z pierwszym.

Czekam tylko na gościa który mi powie "chłopie w ogóle nie zrozumiałeś treści!.. tu chodzi o...":D

chłopie w ogóle nie zrozumiałeś treści!.. tu chodzi o...

koszt połączenia szyny pomiędzy odcinkami i oraz j, gdzie 1≤i<j≤N, można wyznaczyć obliczając koszt połączenia odcinków od i do k oraz odcinków od k+1 do j, gdzie 1≤i≤k<j≤N oraz dodając do niego sumę L[i]+L[k]+L[j].

sugeruje, że oprócz sumy tych trzech L należy jeszcze dodać tam wartość łączenia elementów (1,k) i (k+1,j)

przy czym k nie jest określone - to właśnie ma sprawdzać algorytm - ma sprawdzić dla jakiego k, ta suma będzie najmniejsza

a sprawdzenie tego wymaga sprawdzenie kosztu lewej i prawej części (na lewo i prawo od k), czyli mamy funkcję rekurencyjną o parametrach początkowych

Wartość kosztu naprawy całej szyny to koszt połączenia odcinków od 1 do N.

Oczywiście zadanie masz

rozwiązać rekurencyjnie oraz z wykorzystaniem programowania dynamicznego sprawdzając ile czasu potrzeba na realizację każdego z podejść.
więc musisz to zrobić nie tylko rekurencją (wywołując dla ostatniego łączenia), ale również dynamicznie (zaczynając od najmniejszych kawałków i dopiero z nich wybierać większe kawałki)

ale żeby szyba pękała w N miejscach na N części, to... cóż, pewnie wynika z jakiejś nowej nie znanej nam technologii produkcji szyn... :]

mam nadzieję, że to co napisałem jest chociaż trochę zrozumiałe :)

czyli K jest indexem tablicy???

tak

a mógłbyś mi pokazać jakie rozumowanie prowadzi do wyniku 80?? CO do siebie dodałeś, że wyszedł taki wynik a nie inny??:)

nie mógłbym :D bo mi też wychodzi 66 moim algorytmem

#include <iostream>
#include<limits.h>

using namespace std;

void stack(int depth,int a,int b,int c){
    for(int i=0;i<depth;i++)
        cout<<"          ";
    cout<<a<<" "<<b<<" "<<c<<endl;
}

int bla(int* tab, int i, int j,int st){
    stack(st,i,j,-1);

    if(i==j){
        stack(st,i,j,0);
        return 0;
    }

    int min=INT_MAX;

    for(int k=i;k<j;k++){
        int tmp=bla(tab,i,k,st+1)+bla(tab,k+1,j,st+1)+tab[k];

        if(tmp<min)
            min=tmp;
    }

    stack(st,i,j,min+tab[i]+tab[j]);
    return min+tab[i]+tab[j];
}

int main(int argc, char *argv[])
{
    int tab[]={4,6,10,9,2};
    cout<<bla(tab,0,4,0);
    return 0;
}


 

istotnie jest to łączenie od tyłu tak jak podali w przykładzie

najbliższy 80 wynik jaki udało mi się wygenerować, to 78 :]

a czym jest
cout<<bla(tab,0,4,0); 0,4,0 w wywołaniu tej funkcji??

0 - pierwszy indeks do sprawdzenia
4 - ostatni indeks do sprawdzenia
0 - poziom rekurencji - tylko na potrzeby funkcji stack(...), nie jest częścią algorytmu

A orientuje się ktoś jak tu wyliczyć najlepszą ścieżkę?

a mój algorytm jej nie wylicza? :>