P3141 [USACO16FEB]围栏Fenced In_Platinum

    • 66通过
    • 147提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 动态规划,动规,dp 枚举,暴力 线段树 USACO 2016
  • 难度 提高+/省选-
  • 时空限制 1000ms / 128MB

题解

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

    推荐的相关题目 显示

    题目描述

    Farmer John has realized that many of his cows are strangely agoraphobic (being fearful of large open spaces). To try and make them less afraid of grazing, he partitions his large field into a number of smaller regions by building vertical (north-south) and horizontal (east-west) fences.

    The large field is a rectangle with corner points at $(0,0)$ and $(A,B)$. FJ builds $n$ vertical fences ($0 \leq n \leq 25,000$) at distinct locations $a_1 \ldots a_n$ ($0 < a_i < A$); each fence runs from $(a_i, 0)$ to $(a_i, B)$. He also builds $m$ horizontal fences ($0 \leq m \leq 25,000$) at locations $b_1 \ldots b_m$ ($0 < b_i < B$); each such fence runs from $(0, b_i)$ to $(A, b_i)$. Each vertical fence crosses through each horizontal fence, subdividing the large field into a total of $(n+1)(m+1)$ regions.

    Unfortunately, FJ completely forgot to build gates into his fences, making it impossible for cows to leave their enclosing region and travel around the entire field! He wants to remedy this situation by removing pieces of some of his fences to allow cows to travel between adjacent regions. He wants to select certain pairs of adjacent regions and remove the entire length of fence separating them; afterwards, he wants cows to be able to wander through these openings so they can travel anywhere in his larger field.

    For example, FJ might take a fence pattern looking like this:

    +---+--+
    |   |  |
    +---+--+
    |   |  |  
    |   |  |
    +---+--+

    and open it up like so:

    +---+--+
    |      |  
    +---+  +  
    |      |  
    |      |
    +---+--+

    Please help FJ determine the minimum total length of fencing he must remove to accomplish his goal.

    有一个平面,左下角是(0,0),右上角是(A,B)。

    有n个平行于y轴的栅栏a1..an,表示挡在(ai,0)到(ai,B)之间。

    有m个平行于x轴的栅栏b1..bn,表示挡在(0,bi)到(A,bi)之间。

    这样,平面被划成了(n+1)*(m+1)块。

    现在要去掉某些栅栏的一部分,使得每一块都连通。

    比如原来是这样:

    +---+--+

    | | | +---+--+

    +---+--+

    可以去掉后变成这样:

    +---+--+

    | |
    +---+ +

    +---+--+

    求最少需要去掉多少长度的栅栏使得每一块都连通。

    输入输出格式

    输入格式:

    The first line of input contains $A$, $B$, $n$, and $m$

    ($1 \leq A, B \leq 1,000,000,000$). The next $n$ lines contain $a_1 \ldots a_n$,

    and the next $m$ lines after that contain $b_1 \ldots b_m$.

    输出格式:

    Please write the minimum length of fencing FJ must remove. Note that this might

    be too large to fit into a standard 32-bit integer, so you may need to

    use 64-bit integer types (e.g., "long long" in C/C++).

    输入输出样例

    输入样例#1: 复制
    15 15 5 2
    2
    5
    10
    6
    4
    11
    3
    输出样例#1: 复制
    44
    提示
    标程仅供做题后或实在无思路时参考。
    请自觉、自律地使用该功能并请对自己的学习负责。
    如果发现恶意抄袭标程,将按照I类违反进行处理。