题解 P1220 【关路灯 】

这题没混直接发

瞅了一眼其他题解，大致与我的做法相同，不过貌似都是毫无疑问"一眼得"：区间dp，然后dp状态从天而降，转移方程横空出现，不禁让我想起了我的小白时代，看着这些转移方程两眼一摸黑，所以我决定多说两句也发一篇题解。

题目大意就是一位老大爷跑左跑右去关灯，这些灯每个单位时间都会产生能量耗费，但老大爷没有一响指关掉所有灯的能力，问把这些灯全关完最少需要耗费多少能量。

首先需要明确的是，这位大爷不可能"三过路灯而不关"。也就是说将这些电灯放在一个数轴上，题目所给的路灯位置就作为坐标，所有已经关掉的灯在数轴上的位置形成的必然是一段连续的区间，因为路过一盏灯不关一定不划算（即路过不关灯耗费的能量一定比路过顺手关灯耗费的能量多），关灯不需要时间嘛，自然也不会产生多余的能量耗费，这一点很好理解。

现在我们已经达成了一个共识：大爷已经关掉的灯在数轴上是连续的。有了这个共识以后，我们再思考：既然关掉的灯是连续的，那此时大爷在哪儿？很显然，大爷一定也在这段连续的区间里，否则如果他不在这段区间里，则在外面的一盏灯下，那么区间就不连续了，因此大爷一定在这段连续的区间里。具体的说，大爷要么在这段区间的最左边，要么在区间的最右边，因为大爷是从某一位置开始拓展他的关灯区间，这个区间只能从两边进行拓展，大爷从一开始就在区间端点，每一步动作都是为了关掉下一盏灯，自然不可能在关完一盏灯以后傻傻站在区间中心随着时间流逝。

那么对于某一个关灯区间(l,r)，我们思考下一个问题：如果在这个区间内，耗费的能量取得了最小值，那再由这个区间对外拓展，是不是才有可能获得更大的区间的最小值呢？答案是肯定的。如果存在一种方案在这个区间内取得更小值，则由此再托展的更大的区间一定也能获得更小的值，因为当这个区间的左右端点确定，且大爷到底是在区间最左还是区间最右敲定以后，你会发现，这就是一个子问题，这个子问题取得最优解，更大的问题才能取得最优解，这个子问题的解不受更大问题的干扰，而能确定不受更大问题的干扰而具备的最少必要要素就是状态，即区间的左右端点值和大爷在区间的最左还是最右。

如果你现在说，我们不要大爷的位置了，只要区间左右端点值可不可以？答案是不可以。为什么？因为当你从子问题(l,r)拓展到(l+1,r)的时候，大爷在左或者在右影响了你要去关下一盏灯的距离，从而这就会影响耗费的能量值，所以必须要知道大爷在左还是在右才能去推敲下一个更大问题的所有可能情况，从而选出最优解。

如果你现在又说了，我觉得这三个要素确定的状态(区间两端点+大爷左/右)还不过瘾，我还想知道到底关了多少盏灯了，那么我们考虑，加进来这个要素组成四要素，最后这还是不是个子问题？还能不能推敲出更大问题的最优解？可以，当然可以，但是既然可要可不要，那我们为什么要加进来呢？

因此，我们最后敲定，区间两端点+大爷左/右这三要素为我们的状态，问题又接踵而至，如果我们现在知道了(l,r)这个子问题的最优解，我们怎么去得到更大问题的最优解？

我们考虑大爷一次关一盏灯，也就存在两种大情况(四种小情况)：

1. 对于l-1这一盏灯，大爷可以从l位置或者r位置跑过去关
2. 对于r+1这一盏灯，大爷可以从l位置或者r位置跑过去关

转移就由此诞生。

怎么诞生的？如果你能从这个子问题推到更大的问题，那更大问题的最优解就是所有这些子问题转移来的，都汇总过来以后考虑怎么得出最优解，可能你使用min()或者max()得到最优解，也可能是你自己写的f()得到最优解，本题很明显求最小值，那就是min()作为子问题的最优解。

转移说完了，最后来说说怎么转移，我们首先考虑预处理一个数组sum[ l ] [ r ]，这个数组的含义是当耗费时间为1个单位时间(min)时，下标l到下标r的路灯如果此时还亮着，所要耗费的功率总和，这个数组有什么用我们暂且不说。转移嘛，还是考虑那两种情况，对于区间(l,r)，只可能从(l+1,r)或者(l,r-1)转移而来，我们首先考虑对于(l+1,r)，大爷想去关在l的灯，如果他在l-1处，就需要耗费pos(l)-pos(l-1)的单位时间（注意，文中的位置和题目中灯的位置不同，文中的位置说的是路灯编号，题目中位置说的是数轴间路灯的距离，不要混淆），如果他在r处，想去关l的灯，就需要耗费pos(r)-pos(l)的单位时间，究竟大爷从哪儿去关这个l的灯，那当然是谁小就是从哪儿去关比较划算，这样(l+1,r)的子问题就成了(l,r)的更大问题，从(l,r-1)转移到(l,r)自然也是同理。

小问题最优花费+时间*亮着的灯的单位时间花费 = 大问题最优花费，这时候你就知道sum数组的作用了！而此时此刻，状态转移方程也就不难得出：

dp[l][r][left] = min( dp[l+1][r][left] + (pos(l+1) - pos(l)) * (sum[1][l] + sum[r+1][n]) , dp[l+1][r][right] + (pos(r) - pos(l)) * (sum[1][l] + sum[r+1][n]))

dp[l][r][right] = min(dp[l][r-1][left] + (pos(r) - pos(l)) * (sum[1][l-1] + sum[r][n]) , dp[l][r-1][right] + (pos(r) - pos(r-1)) * (sum[1][l-1] + sum[r][n]))

最后考虑一下边界处理。大爷一开始向左走的话，则有

dp[c-1][c][left] = (pos(c)-pos(c-1))*(sum[1][c-1]+sum[c+1][n])

一开始向右走，则有

dp[c][c+1][right] = (pos(c+1)-pos(c))*(sum[1][c-1]+sum[c+1][n]);

说到这里，如果你还是不能理解dp[l][r][left/right]代表当前已经关掉l到r的灯且大爷此刻在该区间left/right的话，那就只能怪我的表达能力有限了...

附赠AC代码，因为已经说的很清楚了所以我想就不用注释了吧！

#include <bits/stdc++.h>
#define _for(i,a,b) for(int i = (a);i < b;i ++)
#define _rep(i,a,b) for(int i = (a);i > b;i --)
#define INF 0x3f3f3f3f
#define MOD 1000000007
typedef long long ll;
using namespace std;
inline ll read()
{
    ll ans = 0;
    char ch = getchar(), last = ' ';
    while(!isdigit(ch)) last = ch, ch = getchar();
    while(isdigit(ch)) ans = (ans << 1) + (ans << 3) + ch - '0', ch = getchar();
    if(last == '-') ans = -ans;
    return ans;
}
inline void write(ll x)
{
    if(x < 0) x = -x, putchar('-');
    if(x >= 10) write(x / 10);
    putchar(x % 10 + '0');
}
struct lamp
{
    int pos;
    int power;
};
int n,c;
lamp a[53];
int dp[53][53][2];
int sum[53][53];
int main()
{
    n = read(), c = read();
    _for(i,1,n+1)
        a[i].pos = read(),a[i].power = read();

    _for(i,1,n+1)
    {
        sum[i][i] = a[i].power;
        _for(j,i+1,n+1)
            sum[i][j] = sum[i][j-1]+a[j].power;
    }

    memset(dp,0x3f,sizeof(dp));
    if(c>=2)
        dp[c-1][c][0] = (a[c].pos-a[c-1].pos)*(sum[1][c-1]+sum[c+1][n]);
    if(c<=n-1)
        dp[c][c+1][1] = (a[c+1].pos-a[c].pos)*(sum[1][c-1]+sum[c+1][n]);

    _for(len,3,n+1)
        _for(l,1,n-len+2)
        {
            int r = l+len-1;
            dp[l][r][0] = min(dp[l+1][r][0]+(a[l+1].pos-a[l].pos)*(sum[1][l]+sum[r+1][n])
            ,dp[l+1][r][1]+(a[r].pos-a[l].pos)*(sum[1][l]+sum[r+1][n]));
            dp[l][r][1] = min(dp[l][r-1][0]+(a[r].pos-a[l].pos)*(sum[1][l-1]+sum[r][n])
            ,dp[l][r-1][1]+(a[r].pos-a[r-1].pos)*(sum[1][l-1]+sum[r][n]));
        }
    write(min(dp[1][n][0],dp[1][n][1]));
    return 0;
}