Codeforces 139B-Wallpaper

Codeforces 問題文和訳

This problem statement source is Codeforces(http://codeforces.com).
この問題文はCodeforcesのものです。

138-B Wallpaper

http://www.codeforces.com/problemset/problem/139/B
アパートを購入したボリスはすべての部屋に壁紙を貼ることにした。
ボリスのアパートはnこの部屋がある。
部屋のそれぞれは直方体の形をしている。
それぞれの部屋についてメートル単位で壁の縦幅と横幅の長さがわかっている。
異なる部屋は異なる寸法である（高さも含めて）。

ボリスはm種類の壁紙を部屋に貼るために選んだ。
しかし、すべての種類使う必要はない。
それぞれの種類の壁紙は固定された長さと幅で、１ロール単位で売られている。
その長さは当然、いくら壁紙が使用されてないかを示している。
加えてそれぞれの種類の壁紙について１ロールの値段がわかっている。

それぞれの種類の壁紙はそのロールの長さ分細長く伸びている。
それらを貼るとき厳密に垂直に貼らなければならない。(上から下へ貼る)
つまり、壁紙のロールは、その長さが幅よりも短いときでさえ、回転させてはならない。
さらにロールは任意の方法でカットしてもよい。
しかし壁紙同士の繋ぎ目は必ず垂直にならなければならない。
加えてそれぞれの部屋はただひとつの種類の壁紙を貼られなければならない。
そして、同じロールの壁紙を複数の部屋で使用してはならない。
つまり、それぞれの部屋についてバラバラにロールは購入されなければならない。
またロールは使いきらなくても良い。

ボリスはアパートを購入したばかりなので資金不足である。
なので、壁紙には最小のコストしか費やしたくない。
彼を助けろ。

Input

最初の行は正整数nを含む。(1 <= n <= 500)
それはボリスのアパートの部屋の数である。

次のn行はスペース区切りの３つの正整数が与えられる。
それぞれはそれぞれの部屋の奥行きと幅と高さがメートル単位で与えられる。

次の行は正整数mを含む。(1 <= m <= 500)
それは使用できる壁紙の種類数である。

続くm行はそれぞれスペース区切りの３つの正整数を含む。
与えられる壁紙のロールの長さと幅がメートル単位であるのと、
1ロールの値段である。

インプットデータ中のすべての数字は５００を超えない。
それぞれの部屋はこれらの壁紙の種類で貼られることができることを保証されている。

Output

ロールの最小の合計のコストをひとつの数字で出力せよ。

Sample
input

1
5 5 3
3
10 1 100
15 2 320
3 19 500

Output
640

解法

この問題の重要な要素

  • 壁紙の繋ぎ目が必ず垂直でなければならない。
    • （壁の高さと長さ）　と　壁紙のロールの幅　から　必要な壁紙ロールの長さがわかる。
    • 壁紙のロールの長さから、必要なロールの本数がわかる。
  • 同じ部屋は同じ壁紙が貼られなければならない。
    • 部屋に対する壁紙の種類を決め打ち(500 * 500)できる。
  • 同じロールは他の部屋に使いまわせない。（部屋ごとにロールを買わなければならない）
    • それぞれの部屋は独立して考えられる。

よってそれぞれの部屋についてどの壁紙を使えば一番コストが低いか前探索して、
合計すれば良い。

ソース

#include <iostream>
#include <algorithm>

#define REP(i,b,n) for(int i=b;i<(int)n;i++)
#define rep(i,n)   REP(i,0,n)

typedef long long ll;

using namespace std;

const ll MAX = 500;

int main(){
  ll n, m;
  ll height[MAX], width[MAX], length[MAX];
  cin >> n;
  
  rep(i, n){
    cin >>length[i] >> width[i] >> height[i];
  }
  
  cin >> m;
  
  ll rollLen[MAX], rollWid[MAX],cost[MAX], ans = 0;
  rep(i, m){
    cin >> rollLen[i] >> rollWid[i] >> cost[i];
  }
  
  rep(i, n){
    ll mini = (1LL << 60);
    rep(j, m){
      ll len = (length[i] + width[i])*2;
      ll num = len / rollWid[j];
      if(len % rollWid[j] != 0){
	num++;
      }
      ll perRoll = rollLen[j] / height[i];
      
      if(perRoll == 0)continue;
      
      ll res = num / perRoll;
      if(num % perRoll != 0){
	res++;
      }
      mini = min(res * cost[j], mini);
    }
    ans += mini;
  }
  
  cout << ans << endl;
  return 0;
}