题目来源：赛码网-生日礼物（京东2016实习生真题）
题目描述
BF的生日快到了，这一次，小东决定为BF送一份特别的生日礼物为其庆生。作为高智商中的佼佼者，BF在国外求学，因此小东无法与之一起庆生。小东计划送一个生日卡片，并通过特别的包装让BF永远难忘。
她决定把卡片套装在一系列的信封A = {a1, a2, …, an}中。小东已经从商店中购买了很多的信封，她希望能够用手头中尽可能多的信封包装卡片。为防止卡片或信封被损坏，只有长宽较小的信封能够装入大些的信封，同尺寸的信封不能套装，卡片和信封都不能折叠。
输入 输入有若干组，每组的第一行包含三个整数n, w, h，1<=n<=5000, 1<=w, h<=10^6，分别表示小东手头的信封数量和卡片的大小。紧随其后的n行中，每行有两个整数wi和hi，为第i个信封的大小，1<=wi, hi<=10^6。
输出 对每组测试数据，结果第一行中输出最多能够使用的信封数量，结果第二行中按使用顺序输出信封的编号。由于小东有洁癖，她对排在前面的信封比较有好感，若有多个信封可用，她喜欢用最先拿到的信封。另外别忘了，小东要求把卡片装入能够装的最小信封中。 如果卡片无法装入任何信封中，则在单独的行中输出0。
思路
我看题时对题意有两个疑惑，一是w和h的值可否交换，二是信封的大小判断包不包括(w1==w2 && h1<h2) || (w1<w2 && h1==h2)这种情况。第一个问题通过测试数据发现是不允许交换的，第二个问题其实题目中已经说明“只有长宽较小的信封能够装入大些的信封”，所以这种情况也是不允许的。
我整体的思路是使用动态规划完成的，首先存储了尺寸超过卡片的所有信封作为备选，选用map结构存储，使所有信封依次按照w、h从小到大排序。依序遍历每一个备选信封，以当前信封a作为最后一个信封，遍历尺寸比它小的所有信封(因为前面所有的值都会影响当前的结果，所以都需要遍历)，计算出此时能够套装的信封总数的最大值，保存最大值的情况下a的前一个信封的索引号。
编程问题记录
编程调试时出现了堆损坏的错误，问题出在两个地方，
初始化maxnum和previd数组时数组大小错写成了map的大小，应该写成所有信封的数目，因为索引 值对应的初始输入的数目，而非map的数目；把new int[]写成了new int()，造成堆损坏的错误，这个习惯要改正！注意重载<和==时函数规范，函数参数是const &，否则map中使用find查询时结果是错误的。 bool operator < (const size& rhs) const …… bool operator == (const size& rhs) const ……
#include<iostream> #include<map> #include<stack> using namespace std; struct size { int w; int h; bool operator < (const size& rhs) const { return (w < rhs.w) || (w == rhs.w && h<rhs.h); } bool operator == (const size& rhs) const { return w == rhs.w && h == rhs.h; } }; int main() { int num, w, h; stack<int>linkid; while (scanf("%d%d%d", &num, &w, &h) != EOF) { //无效代码 //交换w,h //if (w > h) //{ // int temp = w; w = h; h = temp; //} map<size, int>select; for (int i = 1; i <= num; i++) { int wi, hi; cin >> wi >> hi; //无效代码 //if (wi > hi) //{ // int temp = wi; wi = hi; hi = temp; //} if (wi>w && hi>h) { size env = { wi, hi }; if (select.find(env) == select.end()) select.insert(pair<size, int>(env, i)); } } int packnum = select.size(); if (packnum > 0) { map<size, int>::iterator it = select.begin(); map<size, int>::iterator pit; int maxid = it->second; int *maxnum = new int[num + 1]; maxnum[maxid] = 1; int *previd = new int[num + 1]; previd[maxid] = -1; it++; for (; it != select.end(); it++) { //寻找前一个点 int cnt = 0, pid = -1; for (pit = select.begin(); pit != it; pit++) { if (pit->first.w < it->first.w && pit->first.h < it->first.h) { int curnum = maxnum[pit->second] + 1; if ((curnum>cnt) || (curnum == cnt && pit->second < pid)) { cnt = curnum; pid = pit->second; } } } if (cnt == 0)cnt = 1; maxnum[it->second] = cnt; previd[it->second] = pid; if ((cnt>maxnum[maxid]) || (cnt == maxnum[maxid] && it->second < maxid)) maxid = it->second; } select.clear(); int id = maxid; int count = 0; while (id >= 0) { linkid.push(id); count++; id = previd[id]; } cout << count << endl; delete[] previd; delete[] maxnum; previd = NULL; maxnum = NULL; if (count > 0) { while (!linkid.empty()) { int curid = linkid.top(); linkid.pop(); cout << curid << " "; } cout << endl; } } else { cout << 0 << endl; } } return 0; }