読者です 読者をやめる 読者になる 読者になる

SRM 524 Div2 Easy ShippingCubes

問題

1*1*1のサイズの荷物がN個ある.これを全てa*b*cの箱に入れて送るとき,そのコストはa+b+c.N個の荷物を送る時の最小コストを求めよ.

解答

配列を用意してN以下の荷物に対する最小コストを持つようにする.
a*b*cの荷物に対するコスト(a+b+c)をまず計算.
配列を0からNまで読んでいき,値が決まってないなら,決まっている以前のコスト+1で詰めるはず.

class ShippingCubes {
public:
  int minimalCost(int N) {
    int i, j, k;
    int limit = 200;
    int memot[limit];
    for(i = 1; i <= limit; i++){
      memot[i] = 0;
    }
    for(i = 1; i <= limit; i++){
      for(j = i; j <= limit; j++){
        for(k = j; k <= limit; k++){
          if(i*j*k > limit) continue;
          memot[i*j*k] = i+j+k;
        }
      }
    }
    for(i = 1; i <= limit; i++){
      if (memot[i] <= 0){
        memot[i] = memot[i-1] + 1;
      }
    }
    return memot[N];
  }