fork download
copy 
  1. #include <bits/stdc++.h>
  2. using namespace std;
  3.  
  4. /*
  5. Problem: Maximum Display Score by Merging Two Fish Queues
  6.  
  7. You are given two sequences of fish:
  8. - Tank A of size N
  9. - Tank B of size M
  10.  
  11. Each fish belongs to some family type.
  12.  
  13. You want to form one final display row using all fish from both tanks.
  14.  
  15. Rules:
  16. 1. At any step, you can only take the next fish from the front of Tank A
  17.    or the next fish from the front of Tank B.
  18. 2. The order of fish inside Tank A must remain the same.
  19. 3. The order of fish inside Tank B must remain the same.
  20. 4. Every fish from both tanks must be used exactly once.
  21.  
  22. So the final row is just a merge of A and B while preserving the order
  23. inside each individual tank.
  24.  
  25. ------------------------------------------------------------
  26.  
  27. Scoring:
  28. You are also given a compatibility matrix S.
  29.  
  30. If a fish of family x is placed immediately before a fish of family y,
  31. then you gain:
  32. S[x][y]
  33.  
  34. The total display score is the sum of scores of all adjacent pairs
  35. in the final merged row.
  36.  
  37. ------------------------------------------------------------
  38.  
  39. Task:
  40. Return the maximum possible total display score.
  41.  
  42. ------------------------------------------------------------
  43.  
  44. Example:
  45. A = [1, 2]
  46. B = [3]
  47.  
  48. Possible merged rows:
  49. [1, 2, 3] -> score = S[1][2] + S[2][3]
  50. [1, 3, 2] -> score = S[1][3] + S[3][2]
  51. [3, 1, 2] -> score = S[3][1] + S[1][2]
  52.  
  53. We need the best among all valid merges.
  54.  
  55. ------------------------------------------------------------
  56.  
  57. Idea:
  58. This is a DP problem.
  59.  
  60. Let:
  61. dpA[i][j] = best score after using:
  62. - first i fish from A
  63. - first j fish from B
  64. and the last fish placed came from A
  65.  
  66. dpB[i][j] = same idea, but the last fish placed came from B
  67.  
  68. From each state, we try to place the next fish from A or B
  69. and update the score depending on which fish was placed just before it.
  70.  
  71. Time Complexity: O(N * M)
  72. Space Complexity: O(N * M)
  73. */
  74.  
  75. long long maxDisplayScore(vector<int>& A, vector<int>& B, vector<vector<long long>>& S) {
  76.     int n = (int)A.size();
  77.     int m = (int)B.size();
  78.  
  79.     // A very small value to represent an impossible state
  80.     const long long NEG = -(1LL << 60);
  81.  
  82.     /*
  83.     dpEndA[i][j] = best score after taking:
  84.     - first i fish from A
  85.     - first j fish from B
  86.     and the last fish in the merged sequence is A[i - 1]
  87.     */
  88.     vector<vector<long long>> dpEndA(n + 1, vector<long long>(m + 1, NEG));
  89.  
  90.     /*
  91.     dpEndB[i][j] = best score after taking:
  92.     - first i fish from A
  93.     - first j fish from B
  94.     and the last fish in the merged sequence is B[j - 1]
  95.     */
  96.     vector<vector<long long>> dpEndB(n + 1, vector<long long>(m + 1, NEG));
  97.  
  98.     // Starting with the first fish from A gives score 0
  99.     if (n > 0) dpEndA[1][0] = 0;
  100.  
  101.     // Starting with the first fish from B also gives score 0
  102.     if (m > 0) dpEndB[0][1] = 0;
  103.  
  104.     for (int i = 0; i <= n; i++) {
  105.         for (int j = 0; j <= m; j++) {
  106.  
  107.             // Try to make the current merged sequence end with A[i - 1]
  108.             if (i > 0) {
  109.  
  110.                 // Previous fish also came from A
  111.                 if (i > 1) {
  112.                     dpEndA[i][j] = max(
  113.                         dpEndA[i][j],
  114.                         dpEndA[i - 1][j] + S[A[i - 2]][A[i - 1]]
  115.                     );
  116.                 }
  117.  
  118.                 // Previous fish came from B
  119.                 if (j > 0) {
  120.                     dpEndA[i][j] = max(
  121.                         dpEndA[i][j],
  122.                         dpEndB[i - 1][j] + S[B[j - 1]][A[i - 1]]
  123.                     );
  124.                 }
  125.             }
  126.  
  127.             // Try to make the current merged sequence end with B[j - 1]
  128.             if (j > 0) {
  129.  
  130.                 // Previous fish also came from B
  131.                 if (j > 1) {
  132.                     dpEndB[i][j] = max(
  133.                         dpEndB[i][j],
  134.                         dpEndB[i][j - 1] + S[B[j - 2]][B[j - 1]]
  135.                     );
  136.                 }
  137.  
  138.                 // Previous fish came from A
  139.                 if (i > 0) {
  140.                     dpEndB[i][j] = max(
  141.                         dpEndB[i][j],
  142.                         dpEndA[i][j - 1] + S[A[i - 1]][B[j - 1]]
  143.                     );
  144.                 }
  145.             }
  146.         }
  147.     }
  148.  
  149.     // If both sequences are empty
  150.     if (n == 0 && m == 0) return 0;
  151.  
  152.     // If only B has fish
  153.     if (n == 0) return dpEndB[0][m];
  154.  
  155.     // If only A has fish
  156.     if (m == 0) return dpEndA[n][0];
  157.  
  158.     // Otherwise answer can end with either A or B
  159.     return max(dpEndA[n][m], dpEndB[n][m]);
  160. }
Compilation error #stdin compilation error #stdout 0s 0KB
comments (?)
stdin
copy 
Standard input is empty
compilation info 
/usr/bin/ld: /usr/lib/gcc/x86_64-linux-gnu/8/../../../x86_64-linux-gnu/Scrt1.o: in function `_start':
(.text+0x20): undefined reference to `main'
collect2: error: ld returned 1 exit status
stdout
copy 
Standard output is empty
https://ideone.com/NcXInl
language:
C++14 (gcc 8.3)
created:
4 days ago
visibility:
public

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!