9分求助
查看原帖
9分求助
791137
xhg20121012楼主2024/5/7 21:19
#include <bits/stdc++.h>
using namespace std;

struct node {
	int x, y, cd;
};
int n, dp[1500005];
node a[1500005];

bool cmp(node x, node y) {
	return x.x < y.x;
}

int main() {
	cin >> n;
	for (int i = 0; i < n; i++)
		cin >> a[i].x >> a[i].y, a[i].cd = a[i].y - a[i].x + 1;
	sort(a, a + n, cmp);
	for (int i = 0; i < n; i++) {
		int maxx = 0;
		for (int j = 0; j < i; j++) {
			if (a[i].x > a[j].y) {
				maxx = max(maxx, a[i].cd + a[j].cd);
			}
		}
		dp[i] = maxx + a[i].cd;
	}
	int maxx = 0;
	for (int i = 0; i < n; i++)
		maxx = max(maxx, dp[i]);
	cout << maxx;
	return 0;
}
2024/5/7 21:19
加载中...