【刷题】动态规划——线性DP(最长上升子序列)：友好城市【不相交匹配转化】
·
题目关键是如何把不相交问题转化。
如果AB和A’B’相交，不妨设A<B，则必有A’>B’，也就是说，A’到B’是下降的
如果AB和A’B’不相交，不妨设A<B，则必有A’<B’，也就是说，A’到B’是上升的
因此，对ABCD…从小到大排序，同时也把A’B’C’D’按ABCD的顺序排序，寻找A’B’C’D’中最长的上升子序列，序列长度就是答案。
#include <iostream>
#include <algorithm>
using namespace std;
int n, f[5005], ans;
struct node {
int c1, c2;
}c[5005];
bool cmp(const node &x, const node &y) {
return x.c1 < y.c1;
}
int main() {
scanf("%d", &n);
for (int i = 0; i < n; i++) {
scanf("%d%d", &c[i].c1, &c[i].c2);
}
sort(c, c + n, cmp);
for (int i = 0; i < n; i++) {
for (int j = 0; j < i; j++) {
if (c[i].c2 > c[j].c2) {
f[i] = max(f[i], f[j] + 1);
}
}
ans = max(ans, f[i]);
}
printf("%d\n", ans + 1);
return 0;
}
北京人形旗下天工造物具身智能开源社区，聚焦具身天工与慧思开物两大平台
更多推荐
0
0- 0
已为社区贡献7条内容
所有评论(0)