Codeforces 139 B. Wallpaper

問題

n個の部屋があり、それぞれの幅、奥行き、高さが与えられる。
m種類の壁紙を使って、それぞれの部屋の壁に壁紙を貼る。
それぞれの壁紙の幅と長さと値段が与えられる。

壁紙は、横にだけつなげることができる。
一つの部屋は一種類の壁紙しか使えない。
一つの部屋で余った壁紙を他の部屋に使うことはできない。
使わない種類の壁紙があってもよい。

このとき、全ての部屋に壁紙を貼るのにかかる金額の最小値を求めよ。

制約条件

入力の整数≦500

方針

割り算で、それぞれの壁紙を使ったときに何枚必要を求め、一番安い壁紙を使っていく。

ソースコード

int n,m,a[500],b[500],c[500];
int d[500],e[500],f[500];
void run(){
  cin>>n;
  rep(i,n)cin>>a[i]>>b[i]>>c[i];
  cin>>m;
  rep(i,m)cin>>d[i]>>e[i]>>f[i];
  int ans=0;
  rep(i,n){
    int tmp=(int)1e9;
    rep(j,m){
      int x=2*(a[i]+b[i]), y=d[j]/c[i]*e[j];
      if(y<=0)continue;
      tmp=min(tmp,(x+y-1)/y*f[j]);
    }
    ans+=tmp;
  }
  cout<<ans<<endl;
}