algorithm - 动态编程:允许互换时安装路灯

Question

我很天真，我想这个策略会奏效的：
1）找到照亮一切的最佳方法
2）从最优解中找出k个最昂贵的块（不改变任何条件的解）
3）找到k个最便宜的未使用块
4）将我们的解决方案中昂贵的块换成便宜的块
不幸的是，如果k大于1，这不是最优解。
什么是一个有效的，正确的算法？
Problem G. Fascination Street
输入文件：标准输入
输出文件：标准输出
时限：2秒
内存限制：1024兆字节
一条名为“魅力街”的街道被分成n个等长的街区。对于每个i区（1≤i≤N），
如果i>1，则左侧有块i-1，如果i 与它的名字不同的是，这条街在夜间是一个黑暗而诡异的地方，因此臭名昭著为了解决这个问题，罗伯特
决定在一些街区安装路灯为第i街区安装路灯的费用
是WI，总成本是每个安装成本的总和。安装之后，每个块都应该
有路灯，或者在左或右街区有路灯。
罗伯特也有一些降低成本的诀窍。在安装路灯之前，罗伯特选择了两个不同的街区i和j，并交换了它们的位置运行后，更换安装费用。
换句话说，这个操作只是交换wi和wj的值。这次行动没有成本，但是
罗伯特最多只能表演k次。
现在，给定数组W和最大可能的操作数k，你应该找到整个街道的最小照明成本。
输入
第一行包含两个空格分隔的整数n，k。n是块的数目，k是
最大可能的操作数。（1≤N≤250000，0≤K≤9）
第二行包含n个空格分隔的整数w1，w2··wn，其中wi是安装
第i个街区的路灯。（0≤wi≤109
）
输出
打印一个整数，其中包含整条街照明的最低成本

Answer 1

我不确定这是否会超过你的内存限制，但是计算呢
W（i，k）最小的照明成本i房子，最多k个交换，房子的位置存储在v（i，k）中，房子照明存储在位图BM（i，k）中然后根据前面的值计算w（i，k+1）和w（i+1，k），直到达到i=n，k=k。