链接:http://codeforces.com/problemset/problem/4/D
题意:有一张卡片,若干张信封,它们有个长和宽。要求,找到数量最多的一串信封,这一串信封满足信封的长和宽都是严格递增的,而且卡片的长和宽要比最小的信封小。
思路:先对长度排个序,然后求宽度的最长上升子序列。要处理好长度相等的信封。
![](https://images.cnblogs.com/OutliningIndicators/ContractedBlock.gif)
#include<iostream> #include<cstdio> #include<cmath> #include<cstdlib> #include<cstring> #include<algorithm> #include<vector> using namespace std; const int maxn=5005; int dp[maxn],c[maxn]; struct en { int w,h,f; en(int w=0,int h=0,int f=0):w(w),h(h),f(f) {} }; vector<en> a,fa; bool cmp(const en& x,const en& y) { if(x.w==y.w) return x.h<y.h; else return x.w<y.w; } void LIS(int n) { dp[0]=1; int ans=1,d; memset(c,-1,sizeof(int)*n); c[0]=a[0].f; for(int i=1;i<n;i++) { int s=0; int v; for(int j=0;j<i;j++)//和前面的比较 if(dp[j]>s && a[j].h<a[i].h) { s=dp[j];v=j; } dp[i]=s+1; c[i]=v; if(dp[i]>ans) { ans=dp[i]; d=i;// c[i]=a[j].f; } } printf("%d ",ans); for(int i=0;i<ans;i++) { cout<<c[i]<<' '; } cout<<endl; // int q[n]; // for(int i=0;i<ans;i++) // { // q[ans-i-1]=d; // d=c[d]; // } // for(int i=0;i<ans;i++) // { // int r=a[q[i]].f; // printf("%d ",fa[r].f+1); // } printf(" "); } int main() { freopen("in.cpp","r",stdin); int n,w0,h0; while(~scanf("%d%d%d",&n,&w0,&h0)) { a.clear();fa.clear(); int x,y; for(int i=0; i<n; i++) { en b; scanf("%d%d",&x,&y); b=en(x,y,i); a.push_back(b); fa.push_back(b); } sort(a.begin(),a.end(),cmp); int k=a.size(); for(int i=0; i<a.size(); i++) { if(a[i].w>w0 && a[i].h>h0) { k=i; break; } } if(k==a.size()) { printf("0 "); continue; } for(int i=0;i<k;i++) a.erase(a.begin()); for(int i=0; i<a.size()-1; i++) { if(a[i+1].w == a[i].w) a.erase(a.begin()+i+1); } int l=a.size(); if(l!=1) { l--; if(a[l].w == a[l-1].w) a.erase(a.end()); } LIS(a.size()); } return 0; }
把那个输出还没写好的。