P2541 [USACO16DEC]Robotic Cow Herd机器牛群

    • 7通过
    • 45提交
  • 题目提供者 FarmerJohn2
  • 评测方式 云端评测
  • 标签 USACO 2016
  • 难度 提高+/省选-
  • 时空限制 1000ms-3000ms / 256MB

题解

  • 提示:收藏到任务计划后,可在首页查看。
  • 体验新版界面

    最新讨论 显示

    推荐的相关题目 显示

    题目描述

    Bessie is hoping to fool Farmer John by building a herd of $K$ realistic robotic cows ($1 \leq K \leq 100,000$).

    It turns out that building a robotic cow is somewhat complicated. There are $N$ ($1 \leq n \leq 100,000$) individual locations on the robot into which microcontrollers must be connected (so a single microcontroller must be connected at each location). For each of these locations, Bessie can select from a number of different models of microcontroller, each varying in cost.

    For the herd of robotic cows to look convincing to Farmer John, no two robots should behave identically. Therefore, no two robots should have exactly the same set of microcontrollers. For any pair of robots, there should be at least one location at which the two robots use a different microcontroller model. It is guaranteed that there will always be enough different microcontroller models to satisfy this constraint.

    Bessie wants to make her robotic herd as cheaply as possible. Help her determine the minimum possible cost to do this!

    奶牛Besiie想要得罪一下农夫John,为此她想造一个由K个仿真机械牛组成的牛群来戏弄John (1<=K<=1e5)

    然而她发现想要造出一只机械牛是一件很复杂的事。在一只机械牛身上有N(1<=N<=1e5)个位置必须装上微型控制器。Bessie可以选择不同型号的微型控制器装在每个位置上,每种型号有不同的花费。

    为了让这群机械牛看上去不那么假,牛群中里面不能有两头相同的牛。也就是说,不能有哪两头牛身上的微型控制器是完全相同的。对于任意两头机机械牛来说,至少要有一个位置,在这个位置上这两头牛装了不同的微型控制器。因为美国科技很发达,所以Bessie总能找到足够型号的控制器来满足这个需求。

    现在Bessie希望她的机械牛群造价尽量的便宜,因为剩下的钱她还要用来卡4分35秒出两船兵,她请你帮她计算一下最小花费。

    输入输出格式

    输入格式:

    The first line of input contains $N$ and $K$ separated by a space.

    The following $N$ lines contain a description of the different microcontroller models available for each location. The $i$th such line starts with $M_i$ ($1 \leq M_i \leq 10$), giving the number of models available for location $i$. This is followed by $M_i$ space separated integers $P_{i,j}$ giving the costs of these different models ($1 \le P_{i,j} \le 100,000,000$).

    第一行:N和K,以一个空格分开

    接下来N行:以一个整数Mi开头,表示这个位置可以装Mi种微型控制器,接下来Mi个整数Pi,表示第i个控制器的花费 Pi<=1e8

    输出格式:

    Output a single line, giving the minimum cost to construct $K$ robots.

    一行一个整数,最小花费

    输入输出样例

    输入样例#1: 复制
    3 10 4 1 5 3 10
    3 2 3 3
    5 1 3 4 6 6
    输出样例#1: 复制
    61

    说明

    感谢 @ SakuraDance 提供翻译

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