【玲珑OJ 1097 B -- 萌萌哒的第二题】+ 最长上升子序列

B – 萌萌哒的第二题

Time Limit：5s Memory Limit：128MByte

Submissions：219Solved：74

DESCRipTION

一条东西走向的河两边有都排着工厂，北边有n间工厂A提供原材料，南边有n间工厂B进行生产。现在需要在工厂A和工厂B之间建运输桥以减少运输成本。可是每个工厂B只能接受最多6个工厂A提供的材料能满足生产，而且建立的运输桥之间不能有交叉，北边的工厂A由西向东编号1～n，南边的工厂B也是一样，不能交叉的意思是如果a号工厂A跟b号工厂B之间建立了运输桥，那么不能存在c、d（c < a 且d > b) 使得c号工厂A和d号工厂b之间建立运输桥，每个工厂A只能给一个工厂B提供材料，每个工厂B只能由一间工厂A提供材料，请问在满足上述条件的情况下最多能建立多少个运输桥。（每个工厂最多有6个选择，但只能选一个）

INPUT

包含多组测试数据(<=15)，其中每组测试数据： 第一行一个整数n(1<= n <= 10^5) 接下来n行，第i＋1行6个整数表示i号工厂B能接受的6个工厂A的编号，保证所有编号的范围是1～n，可能重复（请看样例）。

OUTPUT

每组数据输出一行一个整数表示最多能建立的运输桥数量。

SAMPLE INPUT

3 1 2 3 1 2 3 2 2 2 2 2 2 1 3 1 3 1 3 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 2 3 4 5 6 1 1 1 1 1 1

SAMPLE OUTPUT

3 5

吧 B递减，匹配 B的递增，然后求最长上升子序列 ？

AC代码：

#include<cstdio> #include<map> #include<cstring> #include<algorithm> using namespace std; const int K = 1e6 + 10; map <int,int> m; struct node{ int a,b; }st[K]; int ma[K],mb[K]; bool cmp(node i,node j){ if(i.b == j.b) return i.a > j.a; else return i.b < j.b; } int main() { int N,x; while(scanf("%d",&N) != EOF){ int nl = 0; for(int i = 1; i <= N; i++){ m.clear(); for(int j = 1; j <= 6; j++){ scanf("%d",&x); if(!m[x]) m[x]++, st[nl].a = i, st[nl++].b = x; } } sort(st,st + nl,cmp); memset(ma,0,sizeof(ma)); int pl = 0; for(int i = 0; i < nl; i++){ int kl = lower_bound(ma + 1,ma + pl + 1,st[i].a) - ma; if(kl > pl) ma[++pl] = st[i].a; else ma[kl] = st[i].a; } PRintf("%d\n",pl); } return 0; }