【状态压缩 动态规划 数论】1799. N 次操作后的最大分数和

template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{
  *seft = max(*seft, other);
}
class Solution {
public:
  int maxScore(vector<int>& nums) {
    const int n2 = nums.size();
    const int iMaskCount = 1 << n2;
    vector<int> vPre(iMaskCount,-1);
    vPre[0] = 0;
    for (int i = 1; i <= n2 / 2; i++) {
      vector<int> dp(iMaskCount, -1);
      for (int iPre = 0; iPre < iMaskCount; iPre++) {
        
        for (int j1 = 0; j1 < n2; j1++) {
          for (int j2 = j1 + 1; j2 < n2; j2++) {
            const int iAddMask = (1 << j1) | (1 << j2);
            if (iPre & iAddMask) { continue; }
            MaxSelf(&dp[iPre | iAddMask], vPre[iPre] + i * gcd(nums[j1], nums[j2]));
          }
        }
      }
      vPre.swap(dp);
    }
    return vPre.back();
  }
};

template<class T>
void Assert(const vector<T>& v1, const vector<T>& v2)
{
  if (v1.size() != v2.size())
  {
    assert(false);
    return;
  }
  for (int i = 0; i < v1.size(); i++)
  {
    assert(v1[i] == v2[i]);
  }
}
template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
int main()
{
  vector<int> nums;
  {
    Solution slu;
    nums = { 1, 2 };
    auto res = slu.maxScore(nums);
    Assert(1, res);
  }
  {
    Solution slu;
    nums = { 3,4,6,8 };
    auto res = slu.maxScore(nums);
    Assert(11, res);
  }
  {
    Solution slu;
    nums = { 1,2,3,4,5,6 };
    auto res = slu.maxScore(nums);
    Assert(14, res);
  }
}