解析

先按左端點排序得到一個右端點的新隊列，然后就可以發現：
所有合法的方案都是新隊列的一個單調遞增隊列
然后就轉化成了最長上升序列的問題

代碼

#include<bits/stdc++.h> using namespace std; const int N=1e6+100; int m,n; struct node{int a,b;bool operator < (const node y)const{return a<y.a;} }p[N]; int q[N],ed=0; int main(){scanf("%d",&n);for(int i=1;i<=n;i++){scanf("%d%d",&p[i].a,&p[i].b);}sort(p+1,p+1+n);for(int i=1;i<=n;i++){int x=p[i].b;if(q[ed]<x) q[++ed]=x;else{int pl=upper_bound(q+1,q+1+ed,x)-q;q[pl]=x;}}printf("%d",ed); } /* 7 2 6 4 2 9 8 10 3 15 12 17 17 22 4 */

總結

以上是生活随笔為你收集整理的不止代码：友好城市（动态规划）的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。