P2782 友好城市

P2782 友好城市
一道伪装得很好的dp，一开始没想出来，不相交就是所有的都在右边，也就是对于当前的城市i和它的友好城市的坐标都在城市j和它的友好城市的右边，这样就转化成了求最长上升子序列，f[i]表示选到北岸的第i个城市，能最多批准数，不断更新最大值。要小心Max，没有更新的情况，所以要o(max(Max,1))。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<queue>
 4 #include<algorithm>
 5 #include<cmath>
 6 #include<ctime>
 7 #include<set>
 8 #include<map>
 9 #include<stack>
10 #include<cstring>
11 #define inf 2147483647
12 #define For(i,a,b) for(register int i=a;i<=b;i++)
13 #define p(a) putchar(a)
14 #define g() getchar()
15 //by war
16 //2017.11.5
17 using namespace std;
18 struct city
19 {
20     int nor;
21     int sou;
22     bool operator<(const city&a)const
23     {
24         return nor<a.nor;
25     }
26 }a[200010];
27 int t[1000010];
28 int ans=-inf;
29 int now;
30 int n;
31 void in(int &x)
32 {
33     int y=1;
34     char c=g();x=0;
35     while(c<'0'||c>'9')
36     {
37     if(c=='-')
38     y=-1;
39     c=g();
40     }
41     while(c<='9'&&c>='0')x=(x<<1)+(x<<3)+c-'0',c=g();
42     x*=y;
43 }
44 void o(int x)
45 {
46     if(x<0)
47     {
48         p('-');
49         x=-x;
50     }
51     if(x>9)o(x/10);
52     p(x%10+'0');
53 }
54 
55 void modify(int k,int change)
56 {
57     for(;k<=1000000;k+=(-k)&k)
58     t[k]=max(t[k],change);
59 }
60 
61 int get(int k)
62 {
63     int Max=-inf;
64     for(;k>0;k-=(-k)&k)
65     Max=max(Max,t[k]);
66     return Max;
67 }
68 
69 int main()
70 {
71     in(n);
72     For(i,1,n)
73     in(a[i].nor),in(a[i].sou);
74     sort(a+1,a+n+1);
75     For(i,1,n)
76     {
77         now=get(a[i].sou)+1;
78         ans=max(ans,now);
79         modify(a[i].sou,now);
80     }
81     o(max(ans,1));
82      return 0;
83 }