打卡信奥刷题（3252）用C++实现信奥题 P8591 『JROI-8』颅脑损伤 2.0
P8591 『JROI-8』颅脑损伤 2.0
题目描述
给定nnn条线段，第iii条是[li,ri][l_i,r_i][li,ri]。将每一条线段染成红色或黑色，要求：
- 任意两条红色线段不相交。
- 任意一条黑色线段至少和一条红色线段相交。
请最小化红色线段的长度和，并输出这个长度和。
一条线段[li,ri][l_i,r_i][li,ri]的长度定义为ri−lir_i-l_iri−li，两条线段[li,ri],[lj,rj][l_i,r_i],[l_j,r_j][li,ri],[lj,rj]交当且仅当li≤rjl_i\le r_jli≤rj且lj≤ril_j\le r_ilj≤ri。
输入格式
第一行一行一个正整数，代表nnn。
接下来nnn行，每行两个整数，代表li,ril_i,r_ili,ri，用空格隔开。
输出格式
一行一个非负整数，代表红色线段的长度和的最小值。
输入输出样例 #1
输入 #1
5 -6 5 1 3 -4 9 -1 10 6 8输出 #1
4说明/提示
数据范围
| 测试点编号 | n≤n\len≤ |
|---|---|
| 1∼41\sim41∼4 | 101010 |
| 5∼85\sim85∼8 | 400400400 |
| 9∼209\sim209∼20 | 300030003000 |
对于所有数据，满足−109≤li<ri≤109-10^9\le l_i<r_i\le10^9−109≤li<ri≤109。
C++实现
#include<bits/stdc++.h>#definelllonglongusingnamespacestd;intn;structline{ll l,r;booloperator<(constline&x)const{returnthis->l!=x.l?this->l<x.l:this->r<x.r;}}a[3005];ll f[3005],ans=LONG_LONG_MAX;intmain(){scanf("%d",&n);for(inti=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(inti=1;i<=n;i++){ll tot=-2e9;for(intj=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(inti=1;i<=n;i++){if(a[i].r>=a[n].l)ans=min(ans,f[i]);}printf("%lld",ans);return0;}后续
接下来我会不断用C++来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现，记录日常的编程生活、比赛心得，感兴趣的请关注，我后续将继续分享相关内容