LeetCode双周赛139

Tags：DP

题目描述:
定义长度为 2 * x 的序列 seq 的值为：

• (seq[0] OR seq[1] OR … OR seq[x - 1]) XOR (seq[x] OR seq[x + 1] OR … OR seq[2 * x - 1]).

给定一个整数数组nums和一个 正整数k。求出 nums 中所有长度为 2 * k 的子序列的最大值。

数据范围：

• 2 <= nums.length <= 400
• 1 <= nums[i] < $2^7$
• 1 <= k <= nums.length / 2

思路：
要从nums中找出2*k个元素，使得前k个OR的值XOR后k个OR的值最大。这种前后分界各找满足条件的k个元素，可以考虑一手DP。

• f[i][j][x]：前i个元素中取j个能否凑出x.
• g[i][j][x]：从nums[i]起后面的元素中选取j个能否凑出x.

转移方程：
不选nums[i+1]：f[i+1][j][x] = f[i+1][j][x] || f[i][j][x]
选nums[i+1]：f[i+1][j+1][x | num[i+1]] = f[i+1][j+1][x | num[i+1]] || f[i][j][x]

处理出f[n][k][1<<7]和g[n][k][1<<7]，之后枚举f[i][k][x]和g[i+1][k][y].

复杂度：
O(2*n*k*2^7 + n*2^7) = O(n*k*2^8)

Code：

/*
    1.
        f[i][j][x]:前i个元素中取j个元素能否通过or运算凑出x
        g[i][j][x]:从第i个元素其取j个元素能否通过or运算凑出x

        f[i+1][j][x] = (f[i+1][j][x] || f[i][j][x]) // 不选nums[i + 1]
        f[i+1][j+1][x|nums[i+1]] = (f[i+1][j+1][x|nums[i+1]] || f[i][j][x]) // 选nums[i + 1]

    2.  枚举f[i][k][x] 和g[i+1][k][y] 找到最大的 x ^ y
*/
bool f[410][210][1<<7], g[410][210][1<<7];
class Solution {
public:
    int maxValue(vector<int>& nums, int k) {
        int n = nums.size();
        int m = 1 << 7;
        for (int i = 0; i <= n + 1; i++) 
            for (int j = 0; j <= k; j++) 
                for (int x = 0; x < m; x++)
                    f[i][j][x] = g[i][j][x] = false;

        f[0][0][0] = true; // 前0个元素选0个元素能or凑出0
        g[n+1][0][0] = true; // 从第n+1个元素起取0个元素or能凑出0

        for(int i = 0; i < n; i ++)
            for(int j = 0; j <= k; j ++)
                for(int x = 0; x < m; x ++)
                {
                    f[i+1][j][x] = (f[i+1][j][x] || f[i][j][x]); // 不选第i+1个元素
                    f[i+1][j+1][x|nums[i]] = (f[i+1][j+1][x|nums[i]] || f[i][j][x]); // 选第i+1个元素                
                }

        for(int i = n + 1; i > 1; i --)
            for(int j = 0; j <= k; j ++)
                for(int x = 0; x <m; x ++)
                {   
                    g[i-1][j][x] = (g[i-1][j][x] || g[i][j][x]); // 不选第i-1个元素
                    g[i - 1][j + 1][x | nums[i - 2]] = (g[i-1][j+1][x|nums[i-2]] || g[i][j][x]); // 选第i-1个元素
                }
        
        int ans = 0;
        for(int i = k; i <= n - k; i ++)
            for(int x = 0; x < m; x ++)
                for(int y = 0; y < m; y ++)
                    if(f[i][k][x] && g[i+1][k][y])
                        ans = max(ans, x ^ y);
        return ans;
    }
};

Tags：LIS、二分、DP

题目描述:
给你一个长度为 n 的二维整数数组 coordinates 和一个整数 k ，其中 0 <= k < n。
coordinates[i] = [x_i, y_i] 表示二维平面里一个点 (x_i, y_i)。
如果一个点序列 (x1, y1), (x2, y2), (x3, y3), ..., (xm, ym) 满足以下条件，那么我们称它是一个长度为 m 的 上升序列 ：

• 对于所有满足 1 <= i < m 的 i 都有 xi < xi + 1 且 yi < yi + 1 。
• 对于所有 1 <= i <= m 的 i 对应的点 (xi, yi) 都在给定的坐标数组里。

请你返回包含坐标 coordinates[k] 的最长上升路径的长度。

数据范围：

• 1 <= n == coordinates.length <= 105
• coordinates[i].length == 2
• 0 <= coordinates[i][0], coordinates[i][1] <= 109
• coordinates 中的元素 互不相同 。
• 0 <= k <= n - 1

思路：
要从coordinates中尽可能多挑出若干个点其横纵坐标严格递增（点的顺序可打乱）要包含coordinates[k]，即转化为找包含coordinates[k]的二维LIS。

思路1：排序后按照coordinates[k]为分界，用线性DP找出比coordinates[k]严格小的LIS，然后逆序找出以coordinates[k]结尾的递减LIS，前后个数相加即可。O(n^2)会超时。

思路2：直接在严格小于coordinates[k]的点和严格大于coordinates[k]的点中找LIS，coordinates[k]一定可以插入找出LIS，结果为LIS+1。采用线性DP仍会超时，此时采用O(nlogn)找LIS.

O(nlogn)找LIS：
维护一个严格递增的tail数组。遍历数组nums，二分查找tail中第一个tail[k] >= nums[i]，则tail[k] = nums[i]。

• 若tail均小于nums[i]，则tail.push_back(nums[i])。

遍历完nums的tail即为最长上升子序列。

复杂度：
O(nlogn)

Code：

int f[100010];
class Solution {
public:
    int maxPathLength(vector<vector<int>>& coordinates, int k) {
        vector<int> point = coordinates[k];
        sort(coordinates.begin(), coordinates.end(), [&](const auto &p1, const auto &p2)->bool
        {
            if(p1[0] != p2[0]) return p1[0] < p2[0];
            else return p1[1] > p2[1]; // 如果x一样则按y从大到小排序，这样在维护tail数组的时候相同x的只会push进一个y最小的点
        });

        // 只在x > kx && y > ky 和 x < kx && y < ky的点中找LIS
        vector<int> tail;
        for(int i = 0; i < coordinates.size(); i ++)
        {
            int x = coordinates[i][0], y = coordinates[i][1];
            if(x < point[0] && y < point[1] || x > point[0] && y > point[1])
            {
                auto it = lower_bound(tail.begin(), tail.end(), y);
                if(it == tail.end()) tail.push_back(y);
                else
                {
                    if(*it > y) *it = y;
                }
            }
        }
        return tail.size() + 1;
    }
};

Notice:

• vector.end()：指向最后一个元素的下一个位置。
• lower_bound(*st, *ed, A,cmp)：在容器中找到第一个大于等于A的位置。
• upper_bound(*st, *ed, A,cmp)：在容器中找到第一个大于A的位置。