http://codeforces.com/contest/4/problem/D
题意 给你n组高为h 宽为w的数 让你求他们最大的排列
每一个都要大于前面所有的h 和 w 并且大于题中给定你的 mih 和 miw
#include <iostream> #include<algorithm> #include<math.h> #include<string.h> #include<stack> using namespace std; struct node { int w,h,id; }; node a[5040]; int dp[5041]; bool cmp(node a,node b) { if(a.w!=b.w) return a.w<b.w; else return a.h<b.h; } int main() { int n,w,h; cin>>n>>w>>h; for(int i=0;i<n;i++) { cin>>a[i].w>>a[i].h; a[i].id=i; } sort(a,a+n,cmp); int maxn=0,mih=10000000,miw=10000000; for(int i=0;i<n+1;i++) { if(a[i].w>w&&a[i].h>h) dp[i]=1; else dp[i]=0; } for(int i=0;i<n;i++) { for(int j=0;j<i;j++) { if(a[i].h>a[j].h&&a[i].w>a[j].w&&a[i].h>h&&a[i].w>w) { dp[i]=max(dp[j]+1,dp[i]); } if(dp[i]>maxn) { maxn=dp[i]; } } } // for(int i=0;i<n;i++) // cout<<a[i].w<<" "<<a[i].h<<" "<<a[i].id<<endl; // for(int i=0;i<n;i++) // cout<<dp[i]<<" "; // cout<<endl; cout<<maxn<<endl; stack<int>q; for(int i=n-1;i>=0;i--) { if(dp[i]==maxn&&a[i].h>h&&a[i].w>w&&a[i].h<mih&&a[i].w<miw) { mih=a[i].h; miw=a[i].w; maxn--; q.push(a[i].id); } } while(!q.empty()) { cout<<q.top()+1<<" "; q.pop(); } cout<<endl; return 0; } /*45 6134 8495 9045 8632 4145 4991 5368 5303 6245 4894 8529 6378 5797 6165 5444 6826 7091 4030 6680 9984 4155 6711 5100 5977 7333 6514 9729 4141 8171 6185 6146 6016 4488 7588 9333 4921 7368 6350 6552 8552 9900 8327 3310 7281 6402 5749 6124 4381 8190 3834 7421 3816 3475 4977 6239 6577 9277 4139 4037 5329 6808 7446 7679 5283 6775 3023 6777 8500 5921 6975 4501 4383 4623 8409 7070 6430 9429 8736 7353 7760 3942 3683 4859 8424 6348 7379 9043 9054 9012 7114 7050 9454*/