Question

pascal 新题 求高手帮助

在一条笔直的公路上有n盏路灯，每盏灯的功率有大有小，kk站在其中的某一路灯下，他需要在这条路上来回走来关闭所他需要在这条路上来回走来关闭所有的路灯。
现在已知每盏路灯的坐标（m），功率（W），kk的步行速度始终为1m/s。
任务：求kk关闭所有路灯时，消耗的最小功率。
输入
第一行 n （0<n<50） c（表示cy最初所处的位置）
以下n行，每行两个数据，表示路灯的位置和功率。

输出
一个数据，表示最小的消耗功率。

Street.in
5 3
2 10
3 20
5 20
6 30
8 10

Street.out
270

Hint ：关灯的顺序是：3 4 2 1 5 不必输出

Answer 1

（那个KK应该就是cy吧，我默认了 ）
具体解法如下：
解法一（回溯）：
设kk开始所在位置为 c，以起始点 c 为分界点，算出左右两部分总的功率 p_left 和
p_right，再来分别看向左与向右的情况。
向左走时，相应地可以减小左边应费的功，而增加右边应费的功，如果到一个点(一
盏路灯处)所要时间为 t，减少的功为(p_left+w[i])*t，增加的功为 p_right*2t。
向右走时，相应地可以减小右边应费的功，而增加左边应费的功，如果到一个点(一
盏路灯处)所要时间为 t，减少的功为(p_righ+w[i])*t，增加的功为 p_left*2t。
比较向左与向右的情况，找出比较好的一种确定方法。大部分情况能够解出最小值，
但不能求出所有情况下最佳的解。
对于每一个所处位置，都可以选择向左或向右，不管是向左还是向右，相应耗电的变
化都跟上面所述一样。所以可以选择回溯的算法来实现有限的搜索，对每一个点试探向左
与向右的情况，在所有可能的情况中找出最优解。
解法二（动态规划）：
用L记录最左边的被关掉的路灯
用R记录最右边的被关掉的路灯
F(L,R,1)表示此时 KK 停留在了L处
F(L,R,2)表示此时 KK 停留在了R处
则动规方程为：
F[L,R,1]= MIN{F[L+1,R,1]+TOTAL*S[L,L+1] , F[L+1,R,2]+TOTAL*S[L,R]}；
F[L,R,2]= MIN{F[L,R-1,2]+TOTAL*S[R-1,R] , F[L,R-1,1 ]+TOTAL*S[L,R]};
边界条件为：
F[C,C,1]= 0;
F[C,C,2]= 0;
I=C-1 downto 1 :
F[I,C,1]=F[I+1,C,1]+total*(S[I+1]-S[I]);
F[I,C,2]=(total-w[i])*(S[c]-S[i])+f[I,c,1];
I=C+1 to n:
F[C,I,2]=F[C,I-1,2]+total*(S[i]-S[i-1]);
F[C,I,1]=(total-w[i])*(S[i]-S[c])+F[c,i,2];
实现可以用记忆化搜索，递归实现。
注意：

Total一开始的时候为所有电灯的功率和，每关掉一盏路灯，则将Total的值改变！！！
还有，SLR表示从L位置到R位置的长度，因为老张的速度为1m/s，所以，所用时间和距离相等！！！
接下来 按照方程递推即可。

两种方法比较：
回溯比较好理解，但是效率太低，我做这道题是只得了80分。
而动态规划效率很高，每次都是0.02秒过，但是有许多细节要注意。

Answer 2

题目不是很明确啊。何谓 最小的消耗功率 ，如何计算 最小的消耗功率 ？是 cy最初所处的位置 还是 kk最初所处的位置？