可以替换掉机翻的形式化题意
查看原帖
可以替换掉机翻的形式化题意
312811
kyEEcccccc楼主2024/2/24 22:32

有一个长度为 NN 的一次函数序列 {Fi(x)=Aix+Bi}i=1n\{F_i(x) = A_ix+B_i\}_{i=1}^n。我们定义函数序列 PP 的代价为:一开始令 x=0x=0,依次代入序列中的函数使 x←Fi(x)x\gets F_i(x),最终 xx 的值。定义函数(可重)集合 SS 的最小消耗为任意排列这个集合,得到的函数序列的代价的最小值。一种函数序列的 KK-划分 是将其划分成 KK 个连续且非空的子段,并将这些子段视为可重集合(即忽略内部顺序)。这种划分的权值定义为得到的可重集合的最小消耗之和。现在给定一个正整数 XX,保证 X≥∑BiX\ge \sum B_i,你需要将给定的函数序列划分,使得权值不超过 XX(显然存在这样的划分),并使 KK 的值即划分段数最小。求出这个最小值,并给出此时的划分的权值。

2024/2/24 22:32
加载中...