首先假设你要处理第i组城市,但是你一定要把他们连起来
那么可能是都没连, 第1组城市连好后,也有可能是第2组, ...... 第i - 1组, 然后你要连第i组
即:dp[i] = max(dp[i], dp[j] + 1) (0 <= j < i)
但是不能随便连, 怎么办呢?
首先按北城序号, 排个序
要连接第i组城市, 如果前面连好的城市中, 南城序号(前) < 南城序号(i), 那么可以连
(本人语文极差, 听不懂的画个图)
AC code:
#include<bits/stdc++.h>
using namespace std;
int n, dp[5050][3];
struct cheng{
int a, b;
} c[5050];
bool cmp(cheng x, cheng y){
return x.a < y.a;
}
int main(){
cin >> n;
for(int i = 1; i <= n; i++){
cin >> c[i].a >> c[i].b;
}
dp[0][2] = -1;
sort(c + 1, c + n + 1, cmp);
for(int i = 1; i <= n; i++){
for(int j = 0; j < i; j++){
if(dp[j][2] < c[i].b){
if(dp[j][1] + 1 > dp[i][1]){
dp[i][1] = dp[j][1] + 1;
dp[i][2] = c[i].b;
}
}
}
}
int ans = -1;
for(int i = 1; i <= n; i++){
ans = max(ans, dp[i][1]);
}
cout << ans;
return 0;
}