leetcode

Solution to some Leetcode problems written in C++
git clone git://git.dimitrijedobrota.com/leetcode.git
Log | Files | Refs | README | LICENSE

1799.cpp (644B)

      1 class Solution {
      2     int dp[8][16384];
      3 
      4   public:
      5     Solution() { memset(dp, 0xFF, sizeof(dp)); }
      6 
      7     int maxScore(vector<int> &n, int i = 1, int mask = 0) {
      8         if (i > n.size() / 2) return 0;
      9         if (dp[i][mask] != -1) return dp[i][mask];
     10         dp[i][mask] = 0;
     11         for (int j = 0; j < n.size(); j++) {
     12             for (auto k = j + 1; k < n.size(); k++) {
     13                 int new_mask = (1 << j) | (1 << k);
     14                 if ((mask & new_mask)) continue;
     15                 dp[i][mask] = max(dp[i][mask], i * gcd(n[j], n[k]) + maxScore(n, i + 1, mask + new_mask));
     16             }
     17         }
     18         return dp[i][mask];
     19     }
     20 };