/*
*?? ?题目：叠积木
*?? ?题目描述：
?? ??? ?给出一个列表如[[6,7,],[5,4],[3,2]],表示木块的长和宽，当木块的长和宽不大于
?? ?另一个木块的长和宽时，就可以放在上面，此外数组还可以左右翻转。当长宽都大于等于
?? ?上一个积木时才可以搭到上一个积木上，求最多能搭多少层。
?? ?输入描述：
?? ??? ?[[5,4], [6,3], [6,7], [6,6], [4,6]]
?? ?输出描述：
?? ??? ?4
*/
说明：华为0811第一题；
可以参考leetcode300.最长递增子序列，在该题的基础上做一些前期处理;
参考链接：leetcode-300
解题思路：
? ? ? ? 当木块的长和宽都小于另一个木块的长和宽时，就可以放在上面。木块可以左右翻转，可以转化成两个木块之间分别进行最小值比较、最大值比较。我们需要重新定义木块之间的大小关系（特殊的是两个木块之间有三种关系：大于、小于、无法比较），当关系被定义出来，问题就被转化为最长子序列的问题。另外；
? ? ? ? 1、为了方便两个木块比较的函数传参，先对整个木块数组排序，先将每个木块的内部排序，把每个木块的最小值固定在前面，最大值固定在后面，比如[5, 3]->[3, 5]，然后再对整个木块排序，根据最小值排序，最小值相等时，按照最大值排序；
????????[[5,4], [6,3], [6,7], [6,6], [4,6]]->[[3,6], [4,5], [4,6], [6,6], [6,7]]
? ? ? ? 2、重新定义两木块之间的大小关系，由于第一步已经对木块进行变形、对木块整体进行排序，对于木块1:[min1, max1], 木块2：[min2, max2]
如果 min1<=min2的同时max1<=max2，木块1<=木块2
? ? ? ? 3、建立一个dp数组，长度为building.size()，dp[i]代表以building[i]木块为结尾的最长子序列长度，对于第i个木块，拿该木块与i个木块前面的第0个到第i-1个木块比较大小，如果前面的木块小于该木块，就更新dp的值：
代码如下：
#include<iostream>
#include<vector>
#include<algorithm>
using namespace std;
int compareTwoBuildings(vector<int>& nums1, vector<int>& nums2) {
// nums1 < nums2: -1
// return -1:nums1>nums2
// return 1: nums1 < nums2
// return 0:
if (min(nums1[0], nums1[1]) <= min(nums2[0], nums2[1])
&& max(nums1[0], nums1[1]) <= max(nums2[0], nums2[1])) {
return 1;
}
else {
return 0;
}
}
int solution(vector<vector<int>>& building) {
int res = 0;
for (int i = 0; i < building.size(); ++i) {
sort(building[i].begin(), building[i].end());
}
sort(building.begin(), building.end(), [](vector<int>& a, vector<int>& b) {
if (a[0] == b[0]) {
return a[1] < b[1];
}
return a[0] < b[0];
});
// [3, 6], [4, 5], [4, 6], [6, 6], [6, 7]
// dp[i]表示building[i]为结尾的最长子序列
vector<int> dp(building.size(), 1);
for (int i = 1; i < building.size(); ++i) {
for (int j = 0; j < i; ++j) {
if (compareTwoBuildings(building[j], building[i])) {
dp[i] = max(dp[i], dp[j] + 1);
}
res = max(res, dp[i]);
}
}
return res;
}
int main() {
int n;
cin >> n;
vector<vector<int>> building(n, vector<int>(2, 0));
for (int i = 0; i < n; ++i) {
cin >> building[i][0] >> building[i][1];
}
cout << solution(building) << endl;
}执行结果如下：
?
