fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. using ll = long long;
  5.  
  6. /*
  7. QUESTION IN SIMPLE WORDS
  8. ------------------------
  9. We have a list of stations to process in a fixed order.
  10. Each station has a workflow type.
  11.  
  12. There are 2 handlers:
  13. - handler A
  14. - handler B
  15.  
  16. For every station, we choose which handler will process it.
  17.  
  18. Cost rule:
  19. - if that handler processed the same workflow type last time,
  20.   cost is shortTime[type]
  21. - otherwise,
  22.   cost is longTime[type]
  23.  
  24. Goal:
  25. Find the minimum total cost.
  26.  
  27. ------------------------------------------------------------
  28. BRUTE FORCE IDEA
  29. ------------------------------------------------------------
  30. For every station, try both choices:
  31. 1) give it to A
  32. 2) give it to B
  33.  
  34. That gives 2^n possible assignments for n stations.
  35.  
  36. For each full assignment, simulate the total cost.
  37.  
  38. ------------------------------------------------------------
  39. WHY BRUTE FORCE IS TOO SLOW
  40. ------------------------------------------------------------
  41. 2^n grows very fast.
  42.  
  43. Even for around 30 stations, brute force is too expensive.
  44.  
  45. ------------------------------------------------------------
  46. OPTIMIZED IDEA
  47. ------------------------------------------------------------
  48. At any step, to decide the next cost, we only need:
  49. - the current station type
  50. - last workflow type handled by A
  51. - last workflow type handled by B
  52.  
  53. So we use DP.
  54.  
  55. DP state:
  56. (lastA, lastB) -> minimum cost so far
  57.  
  58. That is enough because future cost depends only on these last values.
  59. */
  60.  
  61. ll minimumPrepTime(const vector<int>& stations,
  62.                    const vector<ll>& shortTime,
  63.                    const vector<ll>& longTime) {
  64.     // We pack (lastA, lastB) into one long long so it can be used as a map key.
  65.     auto makeKey = [&](int lastA, int lastB) -> long long {
  66.         return (1LL * (unsigned int)lastA << 32) | (unsigned int)lastB;
  67.     };
  68.  
  69.     // Keep only the minimum cost for a state.
  70.     auto relax = [&](unordered_map<long long, ll>& mp, long long key, ll val) {
  71.         auto it = mp.find(key);
  72.         if (it == mp.end() || val < it->second) {
  73.             mp[key] = val;
  74.         }
  75.     };
  76.  
  77.     unordered_map<long long, ll> dp, nextDp;
  78.  
  79.     // Initially, nobody has processed anything.
  80.     // We use 0 as a dummy workflow type.
  81.     dp[makeKey(0, 0)] = 0;
  82.  
  83.     for (int x : stations) {
  84.         nextDp.clear();
  85.  
  86.         // Try all old states.
  87.         for (auto &it : dp) {
  88.             long long key = it.first;
  89.             ll curCost = it.second;
  90.  
  91.             int lastA = (int)(key >> 32);
  92.             int lastB = (int)(key & 0xffffffffu);
  93.  
  94.             // Option 1: current station goes to A
  95.             ll costIfAHandles = curCost + (lastA == x ? shortTime[x] : longTime[x]);
  96.             relax(nextDp, makeKey(x, lastB), costIfAHandles);
  97.  
  98.             // Option 2: current station goes to B
  99.             ll costIfBHandles = curCost + (lastB == x ? shortTime[x] : longTime[x]);
  100.             relax(nextDp, makeKey(lastA, x), costIfBHandles);
  101.         }
  102.  
  103.         dp.swap(nextDp);
  104.     }
  105.  
  106.     // Final answer = minimum cost among all ending states
  107.     ll ans = LLONG_MAX;
  108.     for (auto &it : dp) ans = min(ans, it.second);
  109.     return ans;
  110. }
  111.  
  112. int main() {
  113.     vector<int> stations = {1, 2, 1, 2, 2};
  114.  
  115.     // Index = workflow type
  116.     vector<ll> shortTime = {0, 2, 3};
  117.     vector<ll> longTime  = {0, 5, 7};
  118.  
  119.     cout << minimumPrepTime(stations, shortTime, longTime) << '\n';
  120.     return 0;
  121. }
Success #stdin #stdout 0.01s 5316KB
comments (?)
stdin
copy 
Standard input is empty
stdout
copy 
20
https://ideone.com/TzwSgg
language:
C++14 (gcc 8.3)
created:
37 days ago
visibility:
secret

Share or Embed source code

Discover > Sphere Engine API

The brand new service which powers Ideone!

Discover > IDE Widget

Widget for compiling and running the source code in a web browser!