首页 > 代码库 > Codeforces Beta Round #4 (Div. 2 Only) D. Mysterious Present
Codeforces Beta Round #4 (Div. 2 Only) D. Mysterious Present
最长上升子序列,这种水题还是一眼就能看出来的。
题目大意:
主人公想在一张w*h的明信片外套信封。他有n个信封,每个信封的长宽给出,问最多能套多少层。给出从小到大的顺序。
解题思路:
最长上升子序列,只不过是记忆路径。
下面是代码:
#include <set> #include <map> #include <queue> #include <math.h> #include <vector> #include <string> #include <stdio.h> #include <string.h> #include <stdlib.h> #include <iostream> #include <cctype> #include <algorithm> #define eps 1e-10 #define pi acos(-1.0) #define inf 107374182 #define inf64 1152921504606846976 #define lc l,m,tr<<1 #define rc m + 1,r,tr<<1|1 #define zero(a) fabs(a)<eps #define iabs(x) ((x) > 0 ? (x) : -(x)) #define clear1(A, X, SIZE) memset(A, X, sizeof(A[0]) * (min(SIZE,sizeof(A)))) #define clearall(A, X) memset(A, X, sizeof(A)) #define memcopy1(A , X, SIZE) memcpy(A , X ,sizeof(X[0])*(SIZE)) #define memcopyall(A, X) memcpy(A , X ,sizeof(X)) #define max( x, y ) ( ((x) > (y)) ? (x) : (y) ) #define min( x, y ) ( ((x) < (y)) ? (x) : (y) ) using namespace std; struct node { int w,h,num; bool operator <(const node a)const { if(w+h==a.w+a.h) { if(w==a.w)return h<a.h; else return w<a.w; } return w+h<a.w+a.h; } } envelopes[5000]; int cnt; int dp[5005],pre[5005]; void output(int num) { if(pre[num]!=-1)output(pre[num]); printf("%d ",envelopes[num].num); return ; } int main() { int n,w,h; cnt=0; scanf("%d%d%d",&n,&w,&h); for(int i=0; i<n; i++) { scanf("%d%d",&envelopes[cnt].w,&envelopes[cnt].h); envelopes[cnt].num=i+1; if(envelopes[cnt].w>w&&envelopes[cnt].h>h)cnt++; } if(cnt==0) { puts("0"); return 0; } clearall(pre,-1); sort(envelopes,envelopes+cnt); int maxnum=1,maxp=0; dp[0]=1; for(int i=1; i<cnt; i++) { int max1=-1,mp=-1; for(int j=i-1; j>=0; j--) { if(envelopes[j].w<envelopes[i].w&&envelopes[j].h<envelopes[i].h&&max1<dp[j]) { max1=dp[j]; mp=j; } } dp[i]=max1+1; pre[i]=mp; if(dp[i]>maxnum) { maxnum=dp[i]; maxp=i; } } printf("%d\n",maxnum); output(maxp); return 0; }
Codeforces Beta Round #4 (Div. 2 Only) D. Mysterious Present
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。