注意力调度问题

[编程题]注意力调度问题

热度指数：363 时间限制：C/C++ 1秒，其他语言2秒空间限制：C/C++ 256M，其他语言512M
算法知识视频讲解

你需要在一个序列建模系统中，给长度为 n 的输入序列做“有限入度”的注意力连边选择，使得信息总量最大。具体约定如下：

每个位置 j 携带一个 d 维实数特征向量 Xj（所有向量均非零），以及一个整数容量 cj，表示该位置最多可以接收来自它之前位置的连边条数。
先对每个向量做 RMSNorm 归一化：对向量的每个分量除以“各分量平方的平均值再开根号”。等价地，若向量为 x，则 rms = sqrt((x[0]^2 + ... + x[d-1]^2)/d)，归一化向量为 x/rms。此处归一化不使用偏置与缩放（gamma=1，epsilon=0）。
对任意一对位置 i<j，计算缩放点积 a(i,j) = (x̂(i) · x̂(j)) / sqrt(d)，再取平方 a(i,j)^2 作为该连边的“贡献值”。
对于每个 j，从所有 i<j 的候选连边里，最多挑 cj 条，使得全局目标 S = Σj Σi<j chosen a(i,j)^2 最大。
输出 round(100 * S) 的整数值。

输入描述:

第一行：n d（空格分隔）
接下来 n 行：每行 d 个浮点数，表示第 j 个向量的 d 个分量
最后一行：n 个非负整数，表示 c0, c1, ..., c(n-1)

输出描述:

一个整数，即 round(100 * S)

示例1

输入

输出

说明

归一化后：x̂0=[1,1]，x̂1=[√2,0]，x̂2=[0,√2]，x̂3=[1,1]
贡献平方：a(0,1)^2=1，a(0,2)^2=1，a(0,3)^2=2，a(1,2)^2=0，a(1,3)^2=1，a(2,3)^2=1
每个 j 最多选 cj 条：j=1 取1；j=2 取1；j=3 取2，共 S=5，输出 round(100*5)=500