友好都市

タイトルの説明
Palmiaには東西を横断する大きな川があり、川にはまっすぐな南北両岸があり、岸にはそれぞれ位置の異なるN都市がある.北岸の各都市には南岸に友好都市が1つしかなく、都市によって友好都市が異なります.
友好都市ごとに政府に川に直線航路を開いて2つの都市を結ぶことを申請したが、川の霧が大きすぎるため、政府は事故を避けるために任意の2つの航路が交差することを避けることにした.プログラミングは政府が申請を承認し、拒否する決定を下すのを助け、任意の2つの航路が交差しないことを保証する場合、承認された申請ができるだけ多くなるようにします.
【入力】
1行目は、1つの整数N(1≦N≦5000)で、都市数を表す.
2行目からn+1行目まで、行ごとに2つの整数で、中間は1つのスペースで区切られ、南岸と北岸の友好都市の座標をそれぞれ表しています.(0≤xi≤10000)
 
【出力】
1行のみで、政府が承認できる最大申請数を示す整数を出力します.
【入力サンプル】

7
22 4
2 6
10 3
15 12
9 8
17 17
4 2

【出力サンプル】

4

 、  

出発点を小さいものから大きいものに並べ替え,到達点を最長で下がらないシーケンスを求める.第一の書き方
for(i=2;i<=n;i++)
{
  maxx=0;
for(j=1;j
  {
    if(a[i].south>a[j].south)&&f[j]>maxx)
     maxx=f[j];
}
   f[i]=maxx+1;
}よく考えてみると、態度はf[i]状態遷移方程式は何ですか.f[i]=max{f[j]}  1<=j
for(i=2;i<=n;i++)
{
for(j=1;j
  {
    if(a[i].south>a[j].south))
     f[i]=max(f[i],f[j]+1);
}
}
次のように参照してください.
#includeusing namespace std;struct t{ int north; int south;};t a[5006];int f[5005];bool cmp (t a,t b){ return a.north}int main(){ int n,i,j; cin>>n; for(int i=1;i<=n;i++) { cin>>a[i].north>>a[i].south; f[i]=1; } sort(a+1,a+n+1,cmp); for(int i=2;i<=n;i++) { int maxx=0; for(j=1;j if(a[i].south>a[j].south&&f[j]>maxx) { maxx=f[j]; } f[i]=maxx+1; } cout< return 0;}
 
二、反省:時間の複雑度が上昇すると、私たちは10^4のデータ規模しかありません.既存の時間の複雑度はO(n^2)であるからです.
昇進すれば時間の複雑さを最適化しますね.stlを使ってもいいです.  upper_bound
 

#include
#include
using namespace std; struct node { int north; int south;//        ，     north（    ） south（    ） }; node a[200005]; int n,i,d[200005],len,temp; bool cmp(node x,node y) { return x.north.north;//                        （     ，                 ） } int main () { scanf("%d",&n); for(i=1;i<=n;i++) { scanf("%d",&a[i].north); scanf("%d",&a[i].south); } sort(a+1,a+1+n,cmp);  d[++len]=a[1].south;  for(i=2;i<=n;i++) { int hh=upper_bound(d+1,d+len+1,a[i].south)-d;//logn       d[hh]=a[i].south; if(hh>len) { len++; } } printf("%d",len); return 0; }