这道题用动态规划的思路解决
根据题意,叠罗汉下面的人比上面的人一定满足(m[i].weight>=m[j].weight&&m[i].height>=m[j].height)
那么,我们可以先根据这个思路将数据从大到小排序,然后求它的最长递减序列
但测试发现,有的数据体重很高,但身高很低,如下图:
根据上面的式子,得到的序列很差;
再分析数据,可以发现,升高体重都很高的人,更容易叠起来,所以排序条件可以变为
bool operator >= (const Member m) {
return (this->height >= m.height && this->weight >= m.weight) ||
((this->height + this->weight > m.height + m.weight));
}
运行结果我的依然和案例的答案不一样,但我的叠罗汉人数比答案的要多,并且数据也都符合题意,感兴趣的可以自己运行一下
#include<iostream>
#include<vector>
using namespace std;
//我找的数据集比你的答案更优哦!
typedef struct Member {
int id, weight, height;
bool operator <= (const Member m) { return this->height <= m.height && this->weight <= m.weight; }
bool operator >= (const Member m) {
return (this->height >= m.height && this->weight >= m.weight) ||
((this->height + this->weight > m.height + m.weight));
}
bool operator > (const Member m) { return this->height > m.height && this->weight > m.weight; }
}Member;
int main() {
int n, count = 0;
Member m;
vector<Member> ms;
while (cin >> n) {
vector<int> dp(n);
for (int i = 0; i < n; i++) {
dp[i] = 1;
}
while (n--) {
cin >> m.id >> m.weight >> m.height;
ms.push_back(m);
}
for (int i = 0; i < ms.size(); i++) {
for (int j = ms.size() - 1; j > i; j--) {
if (ms[j] >= ms[j - 1]) {
swap(ms[j], ms[j - 1]);
}
}
}
//dp[0]=1;
for (int i = 1; i < ms.size(); i++) {
for (int j = i - 1; j >= 0; j--) {
if (ms[i] <= ms[j]) {
dp[i] = max(dp[j] + 1, dp[i]);
}
}
}
for (int i = 0; i < ms.size(); i++) {
count = max(count, dp[i]);
//cout << dp[i] << " " << ms[i].id << " " << ms[i].weight << " " << ms[i].height << endl;
}
int count1 = count,k=-1;
for (int i = ms.size() - 1; i >= 0; i--) {
if (dp[i] == count1) {
if (k < 0 || ms[k]<=ms[i]) {
cout << dp[i] << " " << ms[i].id << " " << ms[i].weight << " " << ms[i].height << endl;
k = i;
count1--;
}
}
}
cout << count << endl;
count = 0;
ms.clear();
}
return 0;
}
/*
40
27
*/

京公网安备 11010502036488号