划分数组得到最小的值之和

题目

划分数组得到最小的值之和

---

给你两个数组 nums 和 andValues，长度分别为 n 和 m。

数组的 值 等于该数组的 最后一个 元素。

你需要将 nums 划分为 m 个 不相交的连续 子数组，对于第 ith 个子数组 [li, ri]，子数组元素的按位AND运算结果等于 andValues[i]，换句话说，对所有的 1 <= i <= m，nums[li] & nums[li + 1] & ... & nums[ri] == andValues[i] ，其中 & 表示按位AND运算符。

返回将 nums 划分为 m 个子数组所能得到的可能的 最小 子数组 值 之和。如果无法完成这样的划分，则返回 -1 。

示例 1：

输入： nums = [1,4,3,3,2], andValues = [0,3,3,2]

输出： 12

解释：

唯一可能的划分方法为：

1. [1,4] 因为 1 & 4 == 0
2. [3] 因为单元素子数组的按位 AND 结果就是该元素本身
3. [3] 因为单元素子数组的按位 AND 结果就是该元素本身
4. [2] 因为单元素子数组的按位 AND 结果就是该元素本身

这些子数组的值之和为 4 + 3 + 3 + 2 = 12

示例 2：

输入： nums = [2,3,5,7,7,7,5], andValues = [0,7,5]

输出： 17

解释：

划分 nums 的三种方式为：

1. [[2,3,5],[7,7,7],[5]] 其中子数组的值之和为 5 + 7 + 5 = 17
2. [[2,3,5,7],[7,7],[5]] 其中子数组的值之和为 7 + 7 + 5 = 19
3. [[2,3,5,7,7],[7],[5]] 其中子数组的值之和为 7 + 7 + 5 = 19

子数组值之和的最小可能值为 17

示例 3：

输入： nums = [1,2,3,4], andValues = [2]

输出： -1

解释：

整个数组 nums 的按位 AND 结果为 0。由于无法将 nums 划分为单个子数组使得元素的按位 AND 结果为 2，因此返回
-1。

提示：

• 1 <= n == nums.length <= 104
• 1 <= m == andValues.length <= min(n, 10)
• 1 <= nums[i] < 105
• 0 <= andValues[j] < 105

题解

方法一:

思路

划分型dp

设$f_{i,j}$是前i个数分成j组的最小代价。
$f_{i,j} = f_{i’,j-1}+nums[i]$，其中$i’$是最优决策点，满足$nums[i’] & nums[i’+1] & … & nums[i] == andValues[j-1]$

由于“与和”的性质，对于固定一段的子数组，随着长度增长，与和减少。并且不同的与和值不超过logU个。利用灵神的模板，可以得到每种“与值”的左右端点，用m颗线段树，第i个线段树维护$f_{…,i}$的区间最小值。

代码

template<class t,class u> ostream& operator<<(ostream& os,const pair<t,u>& p) {
    return os<<'['<<p.first<<", "<<p.second<<']';
}
template<class t> ostream& operator<<(ostream& os,const vector<t>& v) {
    os<<'['; int s = 1;
    for(auto e:v) { if (s) s = 0; else os << ", "; os << e; }
    return os<<']';
}

template<class t,class u> ostream& operator<<(ostream& os,const map<t,u>& mp){
    os<<'{'; int s = 1;
    for(auto [x,y]:mp) { if (s) s = 0; else os << ", "; os<<x<<": "<<y; }
    return os<<'}';
}
const int inf = 0x3f3f3f3f;
struct SegTree {
    #define LS (id << 1)
    #define RS (id << 1 | 1)
    vector<pair<int,int>> v;
    SegTree(int n):v(4*(n+5), {inf,inf}) {
    }
    void push_up(int id) {
        v[id] = min(v[LS], v[RS]);
    }

    void build(int id, int l, int r) {
        // cout << l << " " << r << endl;
        if (l == r) {
            // v[id] = a[l];
            return;
        }
        int m = l + r >> 1;
        build(LS, l, m);
        build(RS, m + 1, r);
        push_up(id);
    }
    // 单点增加v
    void add(int id, int l, int r, int q, int val) {
        if (l == r && l == q) {
            v[id] = {val, q};
            return;
        }
        int m = l + r >> 1;
        if (q <= m)
            add(LS, l, m, q, val);
        if (m < q)
            add(RS, m + 1, r, q, val);
        push_up(id);
    }
    // 区间查询
    pair<int,int> ask(int id, int l, int r, int ql, int qr) {
        if (ql <= l && r <= qr) {
            return v[id];
        }
        int m = l + r >> 1;
        pair<int,int> rt = {inf, inf};
        if (ql <= m)
            rt = min(rt, ask(LS, l, m, ql, qr));
        if (m < qr)
            rt = min(rt, ask(RS, m + 1, r, ql, qr));
        return rt;
    }

};
class Solution {
public:
    int minimumValueSum(vector<int>& a, vector<int>& andValues) {
        int n = a.size(), m = andValues.size();
        vector f(n+1, vector<int>(m+1, inf));
        f[0][0] = 0;
        // cout << "1" << endl;
        vector<SegTree> st;
        for (int i=0; i<=m; i++) {
            st.emplace_back(n);
            st.back().build(1, 0, n);
        }
        // cout << "1" << endl;
        st[0].add(1, 0, n, 0, 0);
        cout << "1" << endl;
        a.push_back(0);
        for (int i=n-1; i>=0; i--) swap(a[i], a[i+1]);

        map<int,pair<int,int>> mp;
        for (int i=1; i<=n; i++) {
            map<int,pair<int,int>> t;
            t[a[i]] = {i,i};
            for (auto [x, y]:mp) {
                int v = a[i]&x;
                if (t.count(v)) {
                    t[v].first = min(t[v].first, y.first);
                    t[v].second = max(t[v].second, y.second);
                } else {
                    t[v] = y;
                }
            }
            mp = t;
            // cout << i << " " << mp << endl;
            for (int j=1; j<=m; j++) {
                if (mp.count(andValues[j-1])) {
                    // cout << "-  " << j << endl;
                    auto [l,r] = mp[andValues[j-1]];
                    // cout << l << " - " << r << endl;
                    auto [v, p] = st[j-1].ask(1, 0, n, l-1, r-1);
                    // cout << v << " " << p << endl;
                    if (p == inf) continue;
                    f[i][j] = f[p][j-1] + a[i];
                    st[j].add(1, 0, n, i, f[i][j]);
                }
            }
            // cout << i << " " << mp << endl;
        }
        return f[n][m] == inf ? -1 : f[n][m];
    }
};