【动态规划 区间dp 位运算】3117. 划分数组得到最小的值之和

template<class ELE,class ELE2>
void MinSelf(ELE* seft, const ELE2& other)
{
  *seft = min(*seft,(ELE) other);
}
template<class ELE>
void MaxSelf(ELE* seft, const ELE& other)
{
  *seft = max(*seft, other);
}
class Solution {
public:
  int minimumValueSum(vector<int>& nums, vector<int>& andValues) {
    const int iBitCnt = 22;
    m_r = andValues.size();
    m_c = nums.size();
    const int iMax = (1 << iBitCnt) - 1;
    vector<vector<int>> dp(m_r+1,vector<int>(m_c, m_iNotMay));
    int iAnd = iMax;
    for (int i = 0; i < m_c; i++) {
      iAnd &= nums[i];
      if (iAnd == andValues[0]) {
        dp[1][i] = nums[i];
      }
    }
    vector<set<int>> vNext(m_c);
    {
      vector<int> next(iBitCnt, m_c);
      for (int i = nums.size() - 1; i >= 0; i--) {
        vNext[i] = set<int>(next.begin(), next.end());
        vNext[i].emplace(i);
        vNext[i].erase(m_c);
        for (int bit = 0; bit < iBitCnt; bit++)
        {
          bool b = (1 << bit) & nums[i];
          if (!b) {
            next[bit] = i;
          }
        }
      }
    }
    for (int r = 1; r < m_r; r++)
    {
      for (int cur = 1; cur < m_c; cur++)
      {
        int iAdd = iMax;
        for (const auto& next : vNext[cur]) {
          iAdd &= nums[next];
          if (andValues[r] == iAdd) {
            MinSelf(&dp[r + 1][next], dp[r][cur - 1] + nums[next]);
          }
        }
        if ((andValues[r - 1] & nums[cur]) == andValues[r - 1]) {
          MinSelf(&dp[r][cur], dp[r][cur - 1]+nums[cur]-nums[cur-1]);
        }       
      }     
    }
    {
      int r = m_r;
      for (int cur = 1; cur < m_c; cur++)
      {       
        if ((andValues[r - 1] & nums[cur]) == andValues[r - 1]) {
          MinSelf(&dp[r][cur], dp[r][cur - 1] + nums[cur] - nums[cur - 1]);
        }
      }
    }
    const int iRet = dp.back().back();
    return (iRet >= 1'000'000) ? -1 : iRet;
  }
  int m_r,m_c;
  const int m_iNotMay = 1'000'000'000;
};

template<class T>
void Assert(const T& t1, const T& t2)
{
  assert(t1 == t2);
}
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]);
  }
}
int main()
{
  vector<int>  nums, andValues;
  int k;
  {
    Solution sln;
    nums = { 1, 9, 8, 8 }, andValues = { 1,8 };
    auto res = sln.minimumValueSum(nums, andValues);
    Assert(9, res);
  }
  {
    Solution sln;
    nums = { 1, 3, 2, 4, 7, 5, 3 }, andValues = { 0, 5, 3 };
    auto res = sln.minimumValueSum(nums, andValues);
    Assert(12, res);
  }
  {
    Solution sln;
    nums = { 1, 4, 3, 3, 2 }, andValues = { 0, 3, 3, 2 };
    auto res = sln.minimumValueSum(nums, andValues);
    Assert(12, res);
  }
  //vector<int>  nums = { 3,6,9 };
  //int k;
  //
  //{
  //  Solution sln;
  //  nums = { 3,6,9 }, k = 3;
  //  auto res = sln.findKthSmallest(nums, k);
  //  Assert(9LL, res);
  //}
}