P8591 『JROI-8』颅脑损伤 2.0

题目描述

给定 $n$ 条线段，第 $i$ 条是 $[l_i,r_i]$。将每一条线段染成红色或黑色，要求：

1. 任意两条红色线段不相交。
2. 任意一条黑色线段至少和一条红色线段相交。

请最小化红色线段的长度和，并输出这个长度和。

一条线段 $[l_i,r_i]$ 的长度定义为 $r_i-l_i$，两条线段 $[l_i,r_i],[l_j,r_j]$ 交当且仅当 $l_i\le r_j$ 且 $l_j\le r_i$。

输入格式

第一行一行一个正整数，代表 $n$。

接下来 $n$ 行，每行两个整数，代表 $l_i,r_i$，用空格隔开。

输出格式

一行一个非负整数，代表红色线段的长度和的最小值。

输入输出样例 #1

输入 #1

5
-6 5
1 3
-4 9
-1 10
6 8

输出 #1

4

说明/提示

数据范围

对于所有数据，满足 $-10^9\le l_i<r_i\le 10^9$。

C++实现

#include<bits/stdc++.h>
#define ll long long
using namespace std;
int n;
struct line{ll l,r;bool operator<(const line &x)const{return this->l!=x.l?this->l<x.l:this->r<x.r;}}a[3005];
ll f[3005],ans=LONG_LONG_MAX;
int main(){
	scanf("%d",&n);
	for(int i=1;i<=n;i++)scanf("%lld%lld",&a[i].l,&a[i].r);
	sort(a+1,a+1+n);
	memset(f,0x3f,sizeof(f));
	f[0]=0;
	a[0].r=-2e9;
	for(int i=1;i<=n;i++){
		ll tot=-2e9;
		for(int j=i-1;j>=0;j--){
			if(a[j].r>=a[i].l||a[j].r<tot)continue;
			f[i]=min(f[i],f[j]+a[i].r-a[i].l);
			tot=max(tot,a[j].l);
		}
	}
	for(int i=1;i<=n;i++){
		if(a[i].r>=a[n].l)ans=min(ans,f[i]);
	}
	printf("%lld",ans);
	return 0;
}

后续

接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容