P3357 最长k可重线段集问题

    • 248通过
    • 1.1K提交
  • 题目提供者 zzlzk
  • 评测方式 云端评测
  • 标签 网络流24题 O2优化 高性能
  • 难度 省选/NOI-
  • 时空限制 1000ms / 128MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 最新讨论 显示

    推荐的相关题目 显示

    题目描述

    给定平面 $x-O-y$ 上 $n$ 个开线段组成的集合 $I$,和一个正整数 $k$ 。试设计一个算法,从开线段集合 $I$ 中选取出开线段集合 $S\subseteq I$ ,使得在 $x$ 轴上的任何一点 $p$,$S$ 中与直线 $x=p$ 相交的开线段个数不超过 $k$,且$\sum\limits_{z\in S}|z|$达到最大。这样的集合 $S$ 称为开线段集合 $I$ 的最长 $k$ 可重线段集。$\sum\limits_{z\in S}|z|$ 称为最长 $k$ 可重线段集的长度。

    对于任何开线段 $z$,设其断点坐标为 $(x_0,y_0)$ 和 $(x_1,y_1)$,则开线段 $z$ 的长度 $|z|$ 定义为:$$ |z|=\lfloor\sqrt{(x_1-x_0)^2+(y_1-y_0)^2}\rfloor$$

    对于给定的开线段集合 $I$ 和正整数 $k$,计算开线段集合 $I$ 的最长 $k$ 可重线段集的长度。

    输入输出格式

    输入格式:

    文件的第一 行有 $2$ 个正整数 $n$ 和 $k$,分别表示开线段的个数和开线段的可重叠数。

    接下来的 $n$ 行,每行有 $4$ 个整数,表示开线段的 $2$ 个端点坐标。

    输出格式:

    程序运行结束时,输出计算出的最长 $k$ 可重线段集的长度。

    输入输出样例

    输入样例#1: 复制
    4 2
    1 2 7 3
    6 5 8 3
    7 8 10 5
    9 6 13 9 
    输出样例#1: 复制
    17

    说明

    $1\leq n\leq500$

    $1 \leq k \leq 13$

    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。