範圍最小值查詢

-1

我具有陣列2D陣列A[n][k]其中n,k<=1000和陣列cost[n][n]，我喜歡這個執行操作（最初所有元件在A是0）範圍最小值查詢

for(int i=1; i<=n; i++) { 

    for(int j=0; j<min(k,i); j++) { 

     int min = Max_Value; 

     for(int r=0; r<i; r++) { 
     min = min(min,A[r][j]+cost[r][i]); 
     } 
     A[i][j+1]=min 
    } 
}

時間的我的代碼複雜度爲O（N ķ N）我可以將其降低到O（N ķ logN）的，我不知道怎麼用線段樹這一點。對於代碼，你可以看到它是動態編程。

來源

2017-03-17 Narendra Modi

1）X，在你的要求Ÿ問題使得複雜的正確回答。請解釋你的問題的含義。乍一看，您正在尋找加權圖中的最小距離。 2）如果成本限制與其兼容，則可以使用Dijkstra算法。 –

-1

我想這樣的事情會工作

創建一個二維數組B[k][n]

for(int i=1;i<=n;i++){ 

    for(int j=0;j<min(k,i);j++){ 

    int min = Query(1,i-1,B[j]); // Min Value 

    A[i][j+1] = min 

    } 

    for(int i=0;i<n;i++){ 

     update A[i] such that B[][i] gets updated 
} 
}

來源

2017-03-17 09:39:25

這也有時間複雜性** O（NKN）** 1.Loop：n，2. Loop：k 3.Loop：n – osanger

範圍最小值查詢

回答

相關問題