这道题用动态规划的思路解决
根据题意,叠罗汉下面的人比上面的人一定满足(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 */