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 }