最小范围查询

Question

我有一个数组 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 K N( 我可以将其简化为 O(NKLOGN( 吗，我不知道如何使用段树。对于代码，您可以看到它是动态编程。

Answer 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   
}
}