algorithms

Algorithm implementations
git clone git://git.laack.co/algorithms.git
Log | Files | Refs | README

main.cpp (1745B)


      1 #include <iostream>
      2 #include <vector>
      3 #include <string>
      4 #include <unordered_map>
      5 
      6 int square(int x) {
      7     return x * x;
      8 }
      9 
     10 std::string vecToString(std::vector<int>& nums) {
     11     std::string res = "";
     12     for(int i = 0; i < nums.size(); ++i) {
     13         res += std::to_string(nums[i]) + ", "; 
     14     }
     15     return res;
     16 }
     17 
     18 int solve(std::vector<int>& nums, std::unordered_map<std::string, int>& memo) {
     19 
     20     std::string nm = vecToString(nums);
     21     if(memo.find(nm) != memo.end()) {
     22         return memo[nm];
     23     }
     24     
     25     int bestScore = 0;
     26 
     27     std::unordered_map<int,int> priors {};
     28     for(int i = 0; i < nums.size(); ++i) {
     29         if(priors.find(nums[i]) == priors.end()) {
     30             priors[nums[i]] = i;
     31         } 
     32 
     33         int firstIdx = priors[nums[i]];
     34         int score = square((i - firstIdx) + 1);
     35 
     36         std::vector<int> removedNums {};
     37 
     38         for(int x = 0; x < nums.size(); ++x) {
     39             if(x >= firstIdx && x <= i) {
     40                 continue;
     41             } else {
     42                 removedNums.push_back(nums[x]);
     43             }
     44         }
     45 
     46         score += solve(removedNums, memo);
     47 
     48         if(score > bestScore) {
     49             bestScore = score;
     50         }
     51     }
     52 
     53     memo[nm] = bestScore;
     54     return bestScore;
     55 
     56 }
     57 
     58 int main() {
     59     // greedily select the highest score first, in any order for ties
     60     int caseCount, numCount, current;
     61     std::cin >> caseCount;
     62     for(int i = 0; i < caseCount; ++i) {
     63         std::cin >> numCount;
     64         numCount *= 2;
     65         std::vector<int> nums {};
     66         for(int x = 0; x < numCount; ++x) {
     67             std::cin >> current;
     68             nums.push_back(current);
     69         }
     70         std::unordered_map<std::string, int> mem {};
     71         std::cout << solve(nums, mem) << std::endl;
     72     }
     73 }