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

 #include<iostream>
#include<cstdio>
#include<queue>
#include<algorithm>
#include<cmath>
#include<ctime>
#include<set>
#include<map>
#include<stack>
#include<cstring>
#define inf 2147483647
#define For(i,a,b) for(register int i=a;i<=b;i++)
#define p(a) putchar(a)
#define g() getchar()
//by war
//2017.11.5
using namespace std;
struct city
{
int nor;
int sou;
bool operator<(const city&a)const
{
return nor<a.nor;
}
}a[];
int t[];
int ans=-inf;
int now;
int n;
void in(int &x)
{
int y=;
char c=g();x=;
while(c<''||c>'')
{
if(c=='-')
y=-;
c=g();
}
while(c<=''&&c>='')x=(x<<)+(x<<)+c-'',c=g();
x*=y;
}
void o(int x)
{
if(x<)
{
p('-');
x=-x;
}
if(x>)o(x/);
p(x%+'');
} void modify(int k,int change)
{
for(;k<=;k+=(-k)&k)
t[k]=max(t[k],change);
} int get(int k)
{
int Max=-inf;
for(;k>;k-=(-k)&k)
Max=max(Max,t[k]);
return Max;
} int main()
{
in(n);
For(i,,n)
in(a[i].nor),in(a[i].sou);
sort(a+,a+n+);
For(i,,n)
{
now=get(a[i].sou)+;
ans=max(ans,now);
modify(a[i].sou,now);
}
o(max(ans,));
return ;
}
05-26 10:20