0

nxn私は正の整数を持つ行列を持っています。各要素のコストを計算する必要があります。

Cost(i, j) = min( val(p, r) + dist(pos(i, j) ,pos(p, r)) ), p, r = 0:n-1.

dist(pos(i, j) ,pos(p, r)) = |i - p| + |j – r|(距離マンハッタン)

私はこれを O(n^4) で次のように解決しました:

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

  for(int j = 0 ; j < n ; j ++) {
    int cost = 9999999;

    for(p = 0 ; p < n ; p ++) {

      for(r = 0 ; r < n ; r ++) {

        if( val[p][r] + abs(i-p) + abs(j-r)) < cost {

           cost = val[p][r] + abs(i-p) + abs(j-r);

        }

       }

     }

}

ここで、O(n^2) の最適解が必要です。私はそれが可能であることを知っており、解決策は動的プログラミングになると聞きましたが、それがどのように可能かわかりません。

4

1 に答える 1

0

n^2で解決しました。アイデアは、行（左右と左右）と列（上下と上下）を繰り返すことです。

void sort（int ** v）{

//オンライン

for（int i = 0; i <n; i ++）{

//left to right
for(int j = 1 ; j < n ; j ++) {
  if(v[i][j-1] + 1 < v[i][j])
    v[i][j] = 1 + v[i][j-1];
}
//right to left
for(int j = n-2 ; j >= 0 ; j --) {
  if(v[i][j+1] + 1 < v[i][j])
    v[i][j] = 1 + v[i][j+1];
}

}

//列上

for（int j = 0; j <n; j ++）{

//up to down
for(int i = 1 ; i < n ; i ++) {
  if(v[i-1][j] + 1 < v[i][j])
    v[i][j] = 1 + v[i-1][j];
}
//down to up
for(int i = n-2 ; i >= 0 ; i --) {
  if(v[i+1][j] +1 <v[i][j])
    v[i][j] = 1 + v[i+1][j];
}

}}

于 2012-11-11T21:25:05.527 に答える