naoya_t@topcoder

SRM357 Div1 Easy: Hotel

過去問, 練習 | 00:45 |

久しぶりに練習。201.66points。(14.65min) ... 時間かかりすぎ

• DPですね。下(0)から行きます

#define sz(a)  int((a).size())
#define all(c)  (c).begin(),(c).end()
#define tr(c,i)  for(typeof((c).begin()) i=(c).begin(); i!=(c).end(); i++)
#define rep(var,n)  for(int var=0;var<(n);var++)

class Hotel {
 public:
  int marketCost(int minCustomers, vector<int> customers, vector<int> cost) {
    int n=sz(customers);
    int maxc = minCustomers + *max_element(all(customers));
    vector<int> v(maxc+1, INT_MAX); v[0] = 0;
    rep(mc,minCustomers) {
      if (v[mc] == INT_MAX) continue;
      rep(i,n){
        int c=customers[i], ct=cost[i];
        v[mc+c] = min(v[mc+c],v[mc]+ct);
      }
    }
    int ct = INT_MAX;
    for(int mc=minCustomers; mc<=maxc; mc++) ct = min(ct,v[mc]);
    return ct;
  }
};