双周赛139
3287. 求出数组中最大序列值
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 2^7 27
- 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运算凑出xg[i][j][x]:从第i个元素其取j个元素能否通过or运算凑出xf[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凑出0g[n+1][0][0] = true; // 从第n+1个元素起取0个元素or能凑出0for(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;}
};
3288.最长上升路径的长度
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 <= 105coordinates[i].length == 20 <= coordinates[i][0], coordinates[i][1] <= 109coordinates中的元素 互不相同 。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的点中找LISvector<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的位置。