回帖：帖子地址： http://tsc13579.spaces.live.com/Blog/cns%21C875510BCE30B997%21330.entry收藏到我的口袋复制给好友 举报
你查询的问题是：关 路灯动态规划
题目大意：
Dobrica得到一份有趣的工作。每天早上他要将村庄里所有的路灯关闭，路灯都是安排在一条道路的一侧的。
Dobrica每天5点开始工作。一开始，他站在某个路灯的旁边。每个路灯有一个功率，也就是每秒钟消耗的能量数。由于Dobrica是个很有经济头脑的人，他希望所有路灯消耗的总能量最少。
Dobrica的速度是每秒钟一米。关闭路灯不需要时间，因为它可以在路过的时候随手关掉。
请你写一个程序，帮助Dobrica安排一个关灯的路线，使得所有路灯所消耗的总的能量最少。

解题思路：
很经典的一道动态规划的题目。
考虑到对于任意一个时刻，关闭的路灯肯定是连续的（古人云，人已至此，不关白不关）。我们这样定义状态：
R —— 第i号到第j号路灯被关闭，且Dobrica在第i号路灯的情况下，消耗的最少能量。
R —— 第i号到第j号路灯被关闭，且Dobrica在第j号路灯的情况下，消耗的最少能量。
有以下转移方程式：
R = Min{ R + (W[1..i]+W)*(D-D) , R + (W[1..i]+W)*(D-D) }
R = Min{ R + (W[1..i-1]+W)*(D-D) , R + (W[1..i-1]+W)*(D-D) }
整个算法的时间复杂度是O(N2)。

启示：连续性是人走路的特征，分析出了这个特征就要用，要么就是基于联通性的DP，要么就是记录某一段已经被走过，左右两边加两个朝外连接的插头，有点类似联通性DP，以前的一道USACO月赛题也是类似的思路才好做，这种走动问题可以用类似的方法来想。

{
Izborne pripreme 2001 - Prvi izborni ispit
Zadatak STRUJA
Autor rjesenja Mladen Kolar
Nesluzbeno rjesenje
}