范围最小值查询

-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

范围最小值查询

回答

相关问题