SRM317 D1M CollectingPayment

仕事が$moment[i]$日にあり報酬は$earning[i]$である．報酬は銀行に振り込まれる形で，振込手数料は$fee$である．振り込む日はこちらが自由に指定できて，報酬の一時的にストックしておける上限などもない．銀行に預けてあるお金は$i \% 7 == 1$の時に利息がついて，その時に銀行に預けてあるお金$ * \frac{rate}{1000}$となる．最終的に銀行に預けてあるお金を最大化する．

$$ dp[i] := i日目に銀行に預けてあるお金の最大値 $$

として動的計画法．$i$日目$\sim j$日目までは一括で銀行に振り込んでもらうとする．その報酬の合計がfee以下ではマイナスになるので，その場合はやらない．$i$日目から$j$日目にかけて利息がつく日が何回あったかをcountしておき， $$ dp[i] * pow(1.0 + \frac{rate}{1000.0}, cnt) + (sum - fee) \to dp[j]$ $$ で更新する．$i$日目までの銀行に預けてあるお金の最大値$*$利息をcount回行い，報酬から振込手数料を引いた金額を足す．ループの最初で利息が付く日の更新をしているため，$j$日目が利息が付く日で合った場合は$-1$している．しかし，このままでは今の最大値のまま銀行にずっと預けておくという遷移をしていないので，最後に$365$日まで預けておく場合を全てやる．

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
55
56
57
58
59
60
61
62
63
64

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

#define REP(i,k,n) for(int i=k;i<n;i++)
#define rep(i,n) for(int i=0;i<n;i++)
#define each(it,v) for(__typeof((v).begin()) it=(v).begin();it!=(v).end();it++)
#define INF 1<<30
#define mp make_pair

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

double dp[400], E[400];

class CollectingPayment {
  public:
  double maximumProfit(vector <int> earning, vector <int> moment, int fee, int rate) {
      int n = earning.size();

      memset(E, 0, sizeof(E));
      rep(i, n) {
          E[moment[i]] = earning[i];
      }

      memset(dp, 0, sizeof(dp));

      rep(i, 366) {
          if(i % 7 == 1)
              dp[i] = dp[i] * (1.0 + double(rate) / 1000.0);

          double sum = 0.0;
          int cnt = 0;
          REP(j, i+1, 366) {
              sum += E[j];
              if(j % 7 == 1) cnt++;
              if(sum < fee) continue;

              dp[j] = max(dp[j], (dp[i] * pow(1.0 + rate / 1000.0, cnt - (j % 7 == 1)) + sum - fee));
          }
      }

      double ans = 0;
      rep(i, 366) {
          ans = max(ans, dp[i]);
          int cnt = 0;
          REP(j, i+1, 366) {
              if(j % 7 == 1) {
                  cnt++;
              }
          }
          ans = max(ans, dp[i] * pow(1.0 + rate / 1000.0, cnt));
      }
      return ans;
  }
};
Oct 26th, 2016
srm, topcoder, 動的計画法