AOJ1509 Rental DVD Shop NEO

Rental DVD Shop NEO | Aizu Online Judge

Introduction to Programming Introduction to Algorithms and Data Structures Library of Data Structures Library of Graph Algorithms Library of Computational Geometry Library of Dynamic Programming Library of Number Theory

セットレンタルを複数回適用することが出来る，とある本以上買う場合は(選んだ本数) となるので，本を 円でレンタルすることが出来る訳なので，複数回買ったのを結局まとめてしまえば，セットレンタルをするのは回で良いことが分かる．

円より高いものはこのセットで買った方がお得で，円より高いものが 本無い場合は，どのへんまでをレンタルしたほうが良いかを判断しなければならないので，値段順に降順ソートして，セットレンタルする範囲と普通に借りる範囲を順番に見て，最小を取った．

Code

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54

#include <iostream>
#include <vector>
#include <string>
#include <cstring>
#include <algorithm>
#include <sstream>
#include <map>
#include <set>

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define INF 1<<30
#define pb push_back
#define mp make_pair

using namespace std;
typedef long long ll;
typedef pair<int,int> P;

int main() {
  ll a, b, c, d, e;
  while(true) {
      cin >> a >> b >> c >> d >> e;

      if(a == 0 && b == 0 && c == 0 && d == 0 && e == 0) break;

      ll na, nb, nc;
      cin >> na >> nb >> nc;

      vector<ll> v;
      rep(i, na) v.push_back(a);
      rep(i, nb) v.push_back(b);
      rep(i, nc) v.push_back(c);

      sort(v.begin(), v.end(), greater<ll>());

      ll sum = a * na + b * nb + c * nc;
      ll ans = sum, pre = 0;

      rep(i, v.size()) {
          pre += v[i];
          sum -= v[i];
          if(i >= d-1) {
              ans = min(ans, sum + min(pre, (i + 1) * e));
          } else {
              ans = min(ans, sum + min(pre, d * e));
          }
      }

      cout << ans << endl;
  }

  return 0;
}
May 10th, 2016
aoj, vol15, 貪欲