解题思路

题意可抽象为：共有 $T$ 次迭代（编号 $0\sim T-1$）。当跳过第 $t+1$ 步（$0\le t<T-1$）时，相当于复用第 $t$ 步的计算结果，会产生损失值 $\text{loss}[t]$。因此一共有 $T-1$ 个“可跳过的位置”（对应步骤 $1\sim T-1$），每个位置选中则付出相应损失。

要求：恰好跳过 $k$ 步，且不能连续跳过两步（即所选位置不能相邻），使总损失最小；若无解输出 $-1$。

这是典型的“带相邻限制的选取最小代价”问题，使用动态规划（DP）：

• 设 $n=T-1$，位置 $i=1\sim n$ 对应损失代价 $c_i=\text{loss}[i-1]$。

题目内容

$Stable/ Diffusion$为代表的图像和视频生成模型采用了一种逐步优化的方法：模型会多次迭代运行同一个核心算法，将初始的随机噪声逐步优化成清晰的图像或视频。随着对生成质量和视频时长要求的提高，核心算法的迭代步骤数持续增大，导致该方法的计算量急剧增加（计算量与步骤数成正比），造成应用部署困难。

为了降低计算负载，可以采用 “缓存复用” 策略：研究发现，相邻步骤的特征往往相似，当第 $t$ 步和第$t+1$步的特征高度相似时，我们可以直接复用第$t$ 步的计算结果，跳过第$t+1$ 步的计算。对于总共 $T$步的优化过程，如果跳过 $k$步，计算量就能降低为原来的$(T-k)/T$。

然而，跳过步骤会带来图像和视频生成质量的损失。用一个长度为 $T-1$ 的损失值列表来记录跳过每一个步骤所带来的损失：列表中的第$t$ 个元素（$0≤t<T$）表示在第$t+1$ 步时复用第$t$步的计算结果（即跳过第$t+1$步计算）所导致的损失值。为了保证生成质量，不能连续跳过$2$ 个及以上步骤（即不能连续复用）。请设计一个函数，在给定总迭代步骤数$T$、需要跳过的步骤数$k$，以及损失值列表的情况下，寻找最优的跳过策略，输出最小的总损失值。

输入描述

1. $T$：正整数 $T$，表示总迭代步骤数（$1<T≤1000$）。
2. $k$：正整数 $k$，表示需要跳过的步骤数（$0≤k<T$）。
3. $loss$：损失值列表，以空格分隔的$T-1$ 个正整数。第 $t$个值（$0≤t<T$）表示跳过第 $t+1$步（复用第$t$ 步的计算结果）所带来的损失值。每个损失值均为小于 $1000$ 的正整数。

输出描述

$output$: 如果没有找到合适的解，输出 $-1$；否则输出最小的总损失值。

样例 1

输入

6
2
2 1 2 4 5

输出

4

说明

跳过第 $1$ 个步骤和第$3$个步骤，总损失值为 $2+2=4$。由于不能连续跳过$2$ 个步骤，因此不能跳过步骤$1$和步骤$2$，或跳过步骤$2$ 和步骤 $3$。

样例 2

输入

6
4
2 1 2 4 5

输出

-1

说明

总迭代步骤数为$5$ 时，无法跳过 $4$ 个不连续的步骤，因此返回$-1$。