{"problem":{"name":"『JROI-8』颅脑损伤 2.0","description":{"content":"给定 $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","description_type":"Markdown"},"platform":"Luogu","limit":{"time_limit":1000,"memory_limit":131072},"difficulty":{"LuoguStyle":"P4"},"is_remote":true,"is_sync":true,"sync_url":null,"sign":"LGP8591"},"statements":[{"statement_type":"Markdown","content":"给定 $n$ 条线段，第 $i$ 条是 $[l_i,r_i]$。将每一条线段染成红色或黑色，要求：\n\n1. 任意两条红色线段不相交。\n2. 任意一条黑色线段**至少**和一条红色线段相交。\n\n请最小化红色线段的长度和，并输出这个长度和。\n\n一条线段 $[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## Input\n\n第一行一行一个正整数，代表 $n$。\n\n接下来 $n$ 行，每行两个整数，代表 $l_i,r_i$，用空格隔开。\n\n## Output\n\n一行一个非负整数，代表红色线段的长度和的最小值。\n\n[samples]\n\n## Note\n\n**数据范围**\n\n|测试点编号|$n\\le$|\n| :----------: | :----------: |\n|$1\\sim4$|$10$|\n|$5\\sim8$|$400$|\n|$9\\sim20$|$3000$|\n\n对于所有数据，满足 $-10^9\\le l_i<r_i\\le10^9$。","is_translate":false,"language":"English"}],"meta":{"iden":"LGP8591","tags":["动态规划 DP","2022","洛谷原创","O2优化","洛谷月赛"],"sample_group":[["5\n-6 5\n1 3\n-4 9\n-1 10\n6 8\n","4"]],"created_at":"2026-03-03 11:09:25"}}