十大免费实用网站,做网站审批号必须要,成都正规搜索引擎优化,域名备案期间 网站访问链接#xff1a;
354. 俄罗斯套娃信封问题
题意#xff1a;
一个信封有长宽#xff0c;如果一个信封的长宽均严格大于另一个信封#xff0c;那么大的这个信封可以装下小的这个信封
求最多能套娃几个信封
解#xff1a;
类似普通的最长上升子序列#xff0c;但是信封…链接
354. 俄罗斯套娃信封问题
题意
一个信封有长宽如果一个信封的长宽均严格大于另一个信封那么大的这个信封可以装下小的这个信封
求最多能套娃几个信封
解
类似普通的最长上升子序列但是信封有两个数据第一时间想到的是优先队列排序但是我们发现这两个数据并没有优先级也不能通过加减乘除之类的操作制造一个新的关键数据
我们看一下正常最长上升子序列的解法动态规划的LIS算法它的DP[i-1]下标初始为0使用后置的方法赋值和保存长度表示长度i的上升子序列最后一位的最小值。
主要过程我将他分为两步更新扩展更新是指我的数值并不足以扩展出更长的上升子序列但是我可以使某个长度的上升子序列最后一位更小结尾越小理论越长扩展则是指我的数值可以完成扩展那我就增加DP计数并保存这个数值。
那假如我们用w升序h在此基础上升序那么对于w来说后进的永远大于等于先进的这是部分符合的所以如果我们遇到w5h15,w10h10,w15h20完全可以用w10h10更新w5h15w10也能满足w15优先选择h最小的但是如果存在同w下h的升序例如w5h15,w10h10,w10h20我们就能发现更新完以后w10h20并不能接在w10h10后面反而应该接在w5h15后面。
我们分析这个错误就可以发现如果w升序排序我们就可以用大的w小的h更新原先小的w大的h如果同w情况下h升序排序更新会先进行先更新的后果/错误就是如果被更新的是目前求出来的最长子序列最后一位的最小值那么本来能扩展长度的数据就会因为这个更新后的w和自身相同无法完成扩展或者更新后的h小于原先的h进行错误扩展看你怎么判断扩展的-当然也会导致其他更新的错误
先更新后扩展不行能不能先扩展后更新实际上这就是答案让w升序的情况下h降序这样同w的情况下大的h就会先进行处理。
在处理一组新的w之前我们已知数组里的old-w都小于这个new-w,那么如果new-w的h大于最后一位就可以进行扩展然后再遍历new-w中h降序的其他数据来更新DP数组我们能确保更新并不会导致已经求出的最长子序列长度变短同时数组里只包含new-w和小于new-w的old-w在条件w1w2h1h2下我们可知用w1h1更新w2h2将会是合法的。
实际代码
#includebits/stdc.h
using namespace std;
struct cmp
{bool operator() (const pairint,int A,const pairint,int B){if(A.firstB.first) return A.secondB.second;else return A.firstB.first;}
};
int maxEnvelopes(vectorvectorint envelopes)
{int lgenvelopes.size(),now0;vectorintdp(lg); priority_queuepairint,int,vectorpairint,int,cmppq;for(const auto envelope:envelopes) pq.push({envelope[0],envelope[1]});while(!pq.empty()){pairint,inttemppq.top();pq.pop();if(now0) dp[now]temp.second;else{if(temp.seconddp[now-1]) dp[now]temp.second;else{auto upperlower_bound(dp.begin(),dp.begin()now,temp.second);if(upperdp.begin()now||upperdp.end()) continue;//没找到*uppermin(*upper,temp.second);}}}return now;
}
int main()
{vectorvectorint envelopes;int n;cinn;for(int i0;in;i){int a,b;cinab;envelopes.push_back({a,b}); }int ansmaxEnvelopes(envelopes);coutansendl;return 0;
}限制
1 envelopes.length 105envelopes[i].length 21 wi, hi 105
