题目大意
给你一张宽为w,长为h的的贺卡，然后给你n个信封,每个信封宽为wi,长为hi，问你最多能在贺卡上嵌套多少个信封，如果某个信封i如果能够装在信封j里，当且仅当w[i]<w[j]&&h[i]<h[j]
题解
就是LIS嘛，没啥好说的。。。
代码：
#include <iostream>
#include <algorithm>
#include <cstdio>
#include <cstring>
using namespace std;
#define MAXN 5006
int pre[MAXN],dp[MAXN];
pair<pair<int,int>,int> a[MAXN];
void dfs(int x)
{
if(pre[x]!=-1) dfs(pre[x]);
printf("%d ",a[x].second+1);
}
int main()
{
int n,w,h;
scanf("%d%d%d",&n,&w,&h);
memset(pre,-1,sizeof(pre));
for(int i=0;i<n;i++)
{
scanf("%d%d",&a[i].first.first,&a[i].first.second);
a[i].second=i;
}
sort(a,a+n);
for(int i=0;i<n;i++)
{
if(w>=a[i].first.first||h>=a[i].first.second) continue;
dp[i]=1;
for(int j=0;j<i;j++)
if(a[i].first.first>a[j].first.first&&a[i].first.second>a[j].first.second&&dp[j]+1>dp[i])
{
dp[i]=dp[j]+1;
pre[i]=j;
}
}
int ans=max_element(dp,dp+n)-dp;
printf("%d\n",dp[ans]);
if(dp[ans])
{
dfs(ans);
printf("\n");
}
return 0;
}