07388. 恰好选 t 个不相邻 未做

$n$ 个位置排成一排，第 $i$ 个位置有价值 $a_i$。要恰好选 $t$ 个位置，且任意两个被选位置不能相邻。选中的价值之和最大是多少？数据保证 $t\le \lceil n/2\rceil$（否则不可能选够）。

第一行两个整数 $n$、$t$。
第二行 $n$ 个整数 $a_i$。

一行一个整数：最大价值之和。

$1\le n\le 3000$，$1\le t\le \lceil n/2\rceil$，$1\le a_i\le 10^9$。