#P3617. dzy loves game

    ID: 2416 传统题 14000ms 888MiB 尝试: 26 已通过: 1 难度: 9 上传者: 标签>难度分类省选/NOI-动态规划线性 DP数据结构根号分块计算几何平方欧氏距离变换排序与序列处理单调栈数论向下取整与向上取整CF2600

dzy loves game

DZY loves game

题目描述

DZY 最近喜欢上了一款游戏。游戏有 nn 关,每关有一名 Boss,每名 Boss 和 DZY 都有 kk 项属性。

DZY 从第 00 关出发,各项属性和累计损失血量初始为 00。要挑战第 ii 关的 Boss,上一关必须是第 AiA_i 至第 i−1i-1 关之一。击败这名 Boss 后,DZY 的属性会变为该 Boss 的属性。

设挑战前累计损失血量为 aa,DZY 的属性为 b1,…,bkb_1,\ldots,b_k,本关 Boss 的属性为 c1,…,ckc_1,\ldots,c_k。打完后,DZY 的累计损失血量变为

a2+∑j=1k(bj−cj)2.\sqrt{a^2+\sum_{j=1}^{k}(b_j-c_j)^2}.

求击败第 nn 关 Boss 后,累计损失血量的最小可能值。

输入格式

第一行两个整数 n,kn,k。

接下来 nn 行,每行 kk 个整数,第 ii 行描述第 ii 关 Boss 的属性。

最后一行 nn 个整数 A1,A2,…,AnA_1,A_2,\ldots,A_n。

输出格式

输出一行一个实数,表示最小累计损失血量,保留三位小数。

样例

1 2
1 1
0
1.414

样例解释

第 00 关的属性均是 00,击败属性为 (1,1)(1,1) 的 Boss 后,累计损失血量为 12+12=2≈1.414\sqrt{1^2+1^2}=\sqrt{2}\approx1.414。

数据范围

n≤50000n\le50000,k≤3k\le3。保证 A1=0A_1=0,其余 Ai>0A_i>0。属性值不超过 100100,由随机方式生成。本题原有三个测试点。

附件

原始题面 PDF:additional_file/original_statement.pdf(供核对)。