ABC013C 節制

C: 節制 - AtCoder Beginner Contest 013 | AtCoder

(null)

部分点 1

として動的計画法．

  • 普通の食事 :
  • 質素の食事 :
  • 食事抜き :

この つの遷移がある．食事抜きの場合にが より大きい場合に限ることに注意する．

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
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70

#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;

ll dp[55][100005];

int main() {
  ll n, h;
  cin >> n >> h;

  ll a, b, c, d, e;
  cin >> a >> b >> c >> d >> e;

  rep(i, 55) {
      rep(j, 100005) {
          dp[i][j] = INF;
      }
  }
  dp[0][h] = 0;

  rep(i, n) {
      rep(j, 100005) {
          if(dp[i][j] == INF) continue;

          if(dp[i+1][j+b] == -1) {
              dp[i+1][j+b] = dp[i][j] + a;
          } else {
              dp[i+1][j+b] = min(dp[i+1][j+b], dp[i][j] + a);
          }

          if(dp[i+1][j+d] == -1) {
              dp[i+1][j+d] = dp[i][j] + c;
          } else {
              dp[i+1][j+d] = min(dp[i+1][j+d], dp[i][j] + c);
          }

          if(j - e > 0) {
              if(dp[i+1][j-e] == -1) {
                  dp[i+1][j-e] = dp[i][j];
              } else {
                  dp[i+1][j-e] = min(dp[i+1][j-e], dp[i][j]);
              }
          }
      }
  }

  ll ans = INF;
  rep(i, 100005) {
      ans = min(ans, dp[n][i]);
  }

  cout << ans << endl;

  return 0;
}

部分点2

普通の食事の回数と，質素な食事の回数を決めれば，残りの日にちが食事抜きとなる．これが より大きければ，そのペアは存在する．その中での最小を取る．

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

#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 n, h;
  cin >> n >> h;

  ll a, b, c, d, e;
  cin >> a >> b >> c >> d >> e;
  
  ll ans = INF;
  rep(i, n + 1) {
      rep(j, n + 1) {
          if(i + j > n) continue;
          int k = n - i - j;

          // cout << h << " " << i * b << " " << j * d << " " << k * e << "  ->  " << h + i * b + j * d - k * e << endl;
          if(h + i * b + j * d - k * e > 0) {
              ans = min(ans, i * a + j * c);
          }
      }
  }

  cout << ans << endl;

  return 0;
}

満点解法

普通の食事の回数を決めれば，後は満足度は単調増加数列になる．この数列の中で初めて を超える時が，その普通の食事の回数の場合の最小金額である． ．

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

#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 1LL<<60
#define pb push_back
#define mp make_pair

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

int main() {
  int n;
  ll h;
  cin >> n >> h;

  ll a, b, c, d, e;
  cin >> a >> b >> c >> d >> e;
  
  ll ans = INF;
  for(ll i = 0; i < n + 1; i++) {
      ll l = -1, r = n - i;
      while(r - l > 1) {
          ll j = (l + r) / 2;
          ll k = n - i - j;

          if(h + i * b + j * d - k * e > 0) {
              r = j;
          } else {
              l = j;
          }
      }

      ll res = i * a + (l + 1) * c;
      ans = min(ans, res);
  }

  cout << ans << endl;

  return 0;
}
Apr 3rd, 2016
2分探索, abc, atcoder, 動的計画法