当前位置: 代码迷 >> 综合 >> CodeForces 4D Mysterious Present (最长递增子序列)
  详细解决方案

CodeForces 4D Mysterious Present (最长递增子序列)

热度:53   发布时间:2023-11-15 13:28:18.0

题目链接:http://codeforces.com/problemset/problem/4/D

#include<bits/stdc++.h>
using namespace std;#define debug puts("YES");
#define rep(x,y,z) for(int (x)=(y);(x)<(z);(x)++)
#define ll long long#define lrt int l,int r,int rt
#define lson l,mid,rt<<1
#define rson mid+1,r,rt<<1|1
#define root l,r,rt
#define mst(a,b) memset((a),(b),sizeof(a))#define pii pair<ll,ll>
#define mk(x,y) make_pair(x,y)
#define fi first
#define se secondconst int  maxn =5e3+5;
const int mod=1e9+7;ll powmod(ll x,ll y){ll t; for(t=1;y;y>>=1,x=x*x%mod) if(y&1) t=t*x%mod; return t;}
ll gcd(ll x,ll y){return y?gcd(y,x%y):x;}int n,h,w;
int dp[maxn],nxt[maxn];
struct node{int h,w,id;bool operator<(const node& y) const{if(w==y.w){if(h==y.h) return id>y.id;return h<y.h;}return w<y.w;}
}e[maxn];void output(int x){if(e[x]) return ;output(nxt[x]);printf("%d ",e[x].id);
}int main(){scanf("%d%d%d",&n,&e[0].w,&e[0].h);e[0].id=0;///拟定编号rep(i,1,n+1){scanf("%d %d",&e[i].w,&e[i].h);e[i].id=i;}sort(e,e+n+1);///排序mst(nxt,-1),mst(dp,-1);int i=0;while(e[i].id) i++;dp[i]=0;rep(j,i,n+1){///int p=j;while(p>i&&e[p].w==e[j].w) p--;///rep(q,i,p+1) if(e[q].h<e[j].h){if(dp[q]!=-1&&dp[q]+1>dp[j]){nxt[j]=q;dp[j]=dp[q]+1;}}}int ans=0,dir=-1;rep(j,i+1,n+1){if(dp[j]>ans){ans=dp[j];dir=j;}}printf("%d\n",ans);output(dir);puts("");return 0;
}

 

  相关解决方案