关路灯（MM不哭）解题报告

本文主要是介绍关路灯（MM不哭）解题报告，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

  关路灯　　

描述

某一村庄在一条路线上安装了n盏路灯，每盏灯的功率有大有小（即同一段时间内消耗的电量有多有少）。老张就住在这条路中间某一路灯旁，他有一 项工作就是每天早上天亮时一盏一盏地关掉这些路灯。为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关，但是老张不知 道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯，然后可以向左也可以向右去关灯。开始他以为先算一下左边路灯的总功率再算一 下右边路灯的总功率，然后选择先关掉功率大的一边，再回过头来关掉另一边的路灯，而事实并非如此，因为在关的过程中适当地调头有可能会更省一些。现在已知 老张走的速度为1m/s，每个路灯的位置（是一个整数，即距路线起点的距离，单位：m）、功率（W），老张关灯所用的时间很短而可以忽略不计。

请你为老张编一程序来安排关灯的顺序，使从老张开始关灯时刻算起所有灯消耗电最少（灯关掉后便不再消耗电了）。

输入

文件第一行是两个数字n(0 < n < 50，表示路灯的总数)和c(1 < ＝ c < =n老张所处位置的路灯号)；

接下来n行，每行两个数据，表示第1盏到第n盏路灯的位置和功率。

输出

一个数据，即最少的功耗(单位：J，1J＝1W·s)。

样例输入

5 3 2 103 205 206 308 10

样例输出

270 {此时关灯顺序为3 4 2 1 5，不必输出这个关灯顺序} 
------------再来看一道题 ：

MM不哭

描述 Description   在一个数轴上,有n个MM(绝非恐龙!)在哭泣(5555~一直哭). tcboy也在这个数轴上,并恰好看到了这一幕,由于每个MM哭都会让tcboy损失一定的rp,于是tcboy有必要去安慰她们.(真命苦啊 T.T) 开始时，tcboy站在k号MM的旁边. 现在知道第i个MM哭泣每秒钟会使tcboy降低 w[i]的rp (单位rp/s). 而tcboy的行走速度很慢只有1m/s .  tcboy安慰MM的方式很特别(怎么安慰随便大家YY了..#@$%^%$#@),不需要花费时间. 请计算tcboy安慰完所有MM,会消耗掉的rp的最小值. 输入格式 Input Format      输入文件的第一行包含一个整数N，2<=N<=1000，表示MM的数量。 第二行包含一个整数V，1<=V<=N，表示开始时tcboy站在几号MM的旁边. 接下来的N行中，每行包含两个用空格隔开的整数D和W，用来描述每个MM，其中0<=D<=1000，0<=W<=1000。D表示MM在数轴上的位置(单位: m)，W表示每秒钟会使tcboy降低W的rp。 输出格式 Output Format   输出只有一行：一个整数，即消耗rp之和的最小值。结果不超过1,000,000,000。

样例输入 Sample Input

4
3
2 2
5 8
6 1
8 7

样例输出 Sample Output 56




    那~显然这两道题是一样的。而且对于我来说。。都是非常非常难的题！
    我们以关路灯为例。。当然这个选择跟MM和大叔没有关系。。只是因为我最初做的就是关路灯啦。
    数据范围已经到1000了的话，这应该是一道（难道不是两道么。。）O（n^2）区间DP了。。最简单的想法是设计f[l][r]是关[l,r]的灯时，[l,r]的灯的最小消耗。但很快我们就发现如果要转移这个状态的话，我们必须加一维坐标维[0/1]记录关[l,r]的最小消耗后物体的位置。但很快我们又发现我们还需要考虑时间，我们试图将时间纳入方程，于是我考虑成了这个样子：
    讲状态改为一个结构体，保存时间(t)和最小耗能(w)，这样就可以设计状态转移
                                                                                            f[l][r][0]=>f[l+1][r][0/1];
                                                                                            f[l][r][1]=>f[l][r-1][0/1];
                 显然，灭完[l,r]的灯后，最优的情况必是物体在l或物体在r，这个是可以证明的。
                        那么对于两种情况，就相当于是这个样子：
                                                f[l][r][0]=>f[l+1][r][0/1]:  O------------
                                                                                           i[i+1------r]
                                                f[l][r][1]=>f[l][r][0/1]:       ------------O
                                                                                          [i-------r-1]r
    但是WA掉了。。于是我们发现t是有后效性的，即在转移过程中可能存在一段中间区间变量使得其w较大而不会被选择但其t却较小，意即其最优解可能不是来自子问题的最小w解。于是我们发现我们的状态转移方程是错误的。
----------------------------------实在不会做了-------------------ORZ---------------------------------------------------------------------
    于是就看了题解，发现题解的转移思路基本一样，最大的区别在于状态。我的状态设计的是关[l,r]的灯、[l,r]的灯的最小耗能，而题解是关[l,r]的灯，所有灯的最小耗能。
                                                                                f[l][r][0]=min(f[l+1][r][0]+(d[l+1]-d[l])*(s[l]+s[n]-s[r]),
                                                                                                       f[l+1][r][1]+(d[r]-d[l])*(s[l]+s[n]-s[r]))
                                                                                f[l][r][1]=min(f[l][r-1][0]+(d[r]-d[l])*(s[l-1]+s[n]-s[r-1]),
                                                                                                       f[l][r-1][1]+(d[r]-d[r-1])*(s[l-1]+s[n]-s[r-1])) 
                                        其中，d[i]表示第i个路灯的坐标，s[i]表示w[1]+...+w[i].
        这样写的话。。
        显然我们可以发现这样一个意义：
                我们脱去了时间的影响，把方程写成了只与w和d相关的。
    但是这又引申出来一个问题，后效性呢？我们知道后效性的存在与否往往取决于对状态的设计。但为什么这样写就没有后效性了呢？
   -------------------------------------------------------------------------------为什么。。。ORZ----------------------------------------
        于是我就四处问学长学姐。。ljs、Lavender、zky、faebdc。。然后faebdc大神终于给我讲明白了。
            我们可以这样考虑， 对于第二个状态，其实我们可以分两部分理解：
                                                            -----------OXXXXX----------
            ①我们已经关了[i,j]的灯。②我们现在在左端点，我们要关若干已知功率和坐标的灯。
            这样的话，我们发现我们可以很轻易地将这个状态转移为另一个全新的状态，这个状态与之前的所有状态都是没有任何关系的！
            意即，我们将问题：在位置X，要关若干已知功率和坐标的灯，的最小能耗。
                   转移为子问题： 在位置Y，要关若干已知功率和坐标的灯，的最小能耗。（其灯集为源问题灯集的真子集）
                            这两个问题显然是完全一样的。
    我们再来尝试将第一个状态转移方程写成类似的形式：
                问题：在位置X， 花费时间t1关了一段区间的灯，的最小能耗。
 转移为子问题： 在位置Y，花费时间t2关了一段区间的灯，的最小能耗。（其灯集为源问题灯集的真子集）
                 这样我们发现，时间t没有被加到状态中，却可以影响状态，这相当于是一个存在后效性的冗余变量，正是它使得我们的方程具有了后效性。。。 
           这样我们发现：消去时间t的意义是巨大的，正是这种思维方式使状态撇去了后效性。
  ------------------------------------------------------总结----------------------------------------------------------------------------------------------
        这道题应该说非常深刻地加深了我对DP的理解：
①无后效性原则、最优子结构，这都是我们在设计状态时需要尤其注意和严格遵循的。对于类似于本题t的变量，我们应该改变思路改变状态消除其存在的意义，才能写出无后效性原则的方程。在设计状态时，我们必须要头脑清醒，认清各状态变量、决策变量的相互关系及存在意义。 
②做题时不可照本宣科循向而去，而是要冷静、积极地思考。
来源：COGS1108（别的不知道了。。）

这篇关于关路灯（MM不哭）解题报告的文章就介绍到这儿，希望我们推荐的文章对编程师们有所帮助！

---