#P2334. [SCOI2006] 城堡

[SCOI2006] 城堡

题目描述

为了救出心爱的公主 Julie,Billy 来到了恶魔的城堡。经过了三天三夜的浴血奋战,魔王殿已近在咫尺。

这是一条狭长的通道,Billy 在位置 00,而魔王殿在位置 n+1n + 1。在每个单位时间,Billy 可以往左或往右移动一个单位,或者原地不动。每个格子的上方都有石头周期性的往下砸,格子 ii 的周期为 cic_i

对于格子 ii 上方的石头,可以用 cic_i 个整数来描述:h1,h2,,hcih_1, h_2, \cdots, h_{c_i},表示在时间 t=kci+xt = kc_i + x1xci1\leq x\leq c_i)时处于该格子上将被砸掉 hxh_x 格血。其中 hx=0h_x = 0 表示该时刻没有石头砸下来。

计算 Billy 最少损失多少格血后可以到达魔王殿。假设 Billy 是不会死的。注意从位置 11 也是可以回到位置 00 的,且在位置 00 不损血。

输入格式

第一行包括一个整数 nn,表示通道的长度。

以下 nn 行,依次表示格子 1,2,,n1, 2, \cdots, n 的情况。每行第一个整数为 cic_i,表示石头下落周期,接下来有 cic_i 个整数,分别为 h1,h2,,hcih_1, h_2, \cdots, h_{c_i}

输出格式

包含一个整数 HP,表示血的最小损失。

4
2 1 0
2 0 1
1 2
7 0 1 1 1 1 1 1

2

提示

对于 50%50\% 的数据,n20n\leq 20

对于 100%100\% 的数据满足:0n10000\leq n\leq 10001ci101\leq c_i\leq 100hx1000\leq h_x\leq 100

  • 2023.4.12 添加一组 hack 数据,不计分。