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输入 #15 -6 5 1 3 -4 9 -1 10 6 8输出 #14说明/提示数据范围测试点编号n≤n\len≤1∼41\sim41∼41010105∼85\sim85∼84004004009∼209\sim209∼20300030003000对于所有数据满足−109≤liri≤109-10^9\le l_ir_i\le10^9−109≤li​ri​≤109。C实现#includebits/stdc.h#definelllonglongusingnamespacestd;intn;structline{ll l,r;booloperator(constlinex)const{returnthis-l!x.l?this-lx.l:this-rx.r;}}a[3005];ll f[3005],ansLONG_LONG_MAX;intmain(){scanf(%d,n);for(inti1;in;i)scanf(%lld%lld,a[i].l,a[i].r);sort(a1,a1n);memset(f,0x3f,sizeof(f));f[0]0;a[0].r-2e9;for(inti1;in;i){ll tot-2e9;for(intji-1;j0;j--){if(a[j].ra[i].l||a[j].rtot)continue;f[i]min(f[i],f[j]a[i].r-a[i].l);totmax(tot,a[j].l);}}for(inti1;in;i){if(a[i].ra[n].l)ansmin(ans,f[i]);}printf(%lld,ans);return0;}后续接下来我会不断用C来实现信奥比赛中的算法题、GESP考级编程题实现、白名单赛事考题实现记录日常的编程生活、比赛心得感兴趣的请关注我后续将继续分享相关内容