poset_Dilworth定理及其应用

引用三篇比较好的文章，是对链，反链，偏序集，Dilworth的讲解和证明

ttang 神牛的笔记，Axl牛，lambda2fei牛

推荐四个可以用此方法做出的习题

对于边界问题，需要带数试一试

HDU 1257

#include
#include
#include
#include
#include
using namespace std;
#define MAXN 20005
int num[MAXN],dp[MAXN];
int main()
{int n;while(scanf("%d",&n) != EOF){for(int i = 0;i < n;i++)scanf("%d",&num[i]);memset(dp,0x3f,sizeof(dp));int ans = 0;for(int i = 0;i < n;i++){int ind = lower_bound(dp,dp + n,num[i]) - dp;dp[ind] = num[i];ans = max(ans,ind);}printf("%d\n",ans + 1);}
}

#include
#include
#include
#include 
#include
using namespace std;
typedef pairpii;
#define MAXN 50010
int dp[MAXN];
pii num[MAXN];
int main()
{int _,n;scanf("%d",&_);while(_--){scanf("%d",&n);for(int i = 0;i < n;i++)scanf("%d%d",&num[i].first,&num[i].second);sort(num,num + n);memset(dp,0,sizeof(dp));int ans = 0;for(int i = 0;i < n;i++){int ind = lower_bound(dp,dp + n,num[i].second,greater()) - dp;dp[ind] = num[i].second;ans = max(ans,ind);}printf("%d\n",ans + 1);}
}

#include
#include
#include
#include
#include
using namespace std;
typedef pairpii;
#define x first
#define y second
#define MAXN 900
pii num[MAXN];
int dp[MAXN];
int main()
{int n;while(scanf("%d%d",&num[0].x,&num[0].y),num[0].x + 1 | num[0].y + 1){n = 1;while(scanf("%d%d",&num[n].x,&num[n].y),num[n].x | num[n].y)n++;sort(num,num + n);memset(dp,0,sizeof(dp));int ans = 0;for(int i = 0;i < n;i++){int ind = lower_bound(dp,dp + n,num[i].y,greater()) - dp;dp[ind] = num[i].y;ans = max(ans,ind);}printf("%d\n",ans + 1);}
}

#include
#include
#include
#include
#include
using namespace std;
struct pii
{int x,y;bool operator < (const pii & p)const{return x == p.x ? y > p.y : x < p.x;}
};
#define MAXN 20005
pii num[MAXN];
int dp[MAXN];
int main()
{int n,_;scanf("%d",&_);while(_--){scanf("%d",&n);for(int i = 0;i < n;i++)scanf("%d%d",&num[i].x,&num[i].y);sort(num,num + n);memset(dp,0,sizeof(dp));int ans = 0;for(int i = 0;i < n;i++){int ind = upper_bound(dp,dp + n,num[i].y,greater()) - dp;dp[ind] = num[i].y;ans = max(ans,ind);}printf("%d\n",ans + 1);}
}

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！