搜索
您的当前位置:首页正文

【刷题】动态规划——线性DP(最长上升子序列):友好城市【不相交匹配转化】

来源:独旅网

题目关键是如何把不相交问题转化。

如果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;
}

因篇幅问题不能全部显示,请点此查看更多更全内容

热门图文

Top