题解 P1220 【关路灯 】

ButterflyDew · 2018-02-28 11:25:12 · 题解

分析题目先--“然后可以向左也可以向右去关灯”也就是说，每关完一个灯就有两个选择。

于是我们产生了如下的备选方案

1. dfs+玄学减枝
2. 贪心
3. dp

一个一个来。 对于方案一，2^n的复杂度显然是不行的，我们需要用一些方法去掉某些明显不成立的分支。

比如说，老张在位置i，他左边的灯比右边的灯功率大还近，是不是一定去关呢？或者我们用数学方法推得i在j前面的条件，又或者我们在线更新答案进行减枝。

对于方案二，可以利用数学方法寻找先后条件，也可以结合方案一减枝。这里不过多赘述。（其实是我不会）

重点在方案三

n<=50 我们可以考虑比较多的维度的dp

我们思考，朝一个方向走后，我们更新了什么状态呢？

答案是左边待开的灯和右边待开的灯的编号，这是很直观的。

我们考虑dp[i][j]代表区间i，j的灯已经全部关闭时的时间点已经浪费的电量

继续向下思考，我们发现还漏了一个状态，就是当前这个时间点老张是在i点还是j点。

这好办，加一维就行了

则dp[i][j][k]代表区间i，j的灯已经全部关闭时老王在 i 处(k==0)或 j 处(k==1)的时间点已经浪费的电量

我们尝试写出状态转移方程

dp[i][j][0]=min(dp[i+1][j][0]+cal(),
                dp[i+1][j][1]+cal());
dp[i][j][1]=min(dp[i][j-1][0]+cal(),
                dp[i][j-1][1]+cal());

其中，cal()函数计算从上一个区间转移过来时没关的路灯消耗的电力

这里详细一些的说一下cal()函数。

我们要计算某阶段消耗的电力，则需要知道这一段的路程（即时间）和没有关的电灯的功率之和。

想要尽快的计算，我们可以利用前缀和O(1)找到功率之和。 令p[i]为功率的前缀和数组，loc[i]存储路灯位置。

int cal(int i,int j,int l,int r)
{
    return (loc[j]-loc[i])*(p[l]+p[n]-p[r-1]);
}

则cal()如上

于是完整的转移方程

 dp[i][j][0]=
 min(dp[i+1][j][0]+cal(i,i+1,i,j+1),
     dp[i+1][j][1]+cal(i,j,i,j+1));
 dp[i][j][1]=
 min(dp[i][j-1][0]+cal(i,j,i-1,j),
     dp[i][j-1][1]+cal(j-1,j,i-1,j));

然而还没完。

转移的顺序和边界的确定也是这个题的一个难点（反正我是开始没注意到QAQ）

很自然的觉得，这个dp就像扩散那样，从中间直接往两边更新即可

于是我们写出

    dp[c][c+1][1]=cal(c,c+1,c-1,c+1);
    dp[c-1][c][0]=cal(c-1,c,c-1,c+1);
    for(int i=c-1;i>0;i--)
        for(int j=c+1;j<=n;j++)
        {
            dp[i][j][0]=min(dp[i+1][j][0]+cal(i,i+1,i,j+1),dp[i+1][j][1]+cal(i,j,i,j+1));
            dp[i][j][1]=min(dp[i][j-1][0]+cal(i,j,i-1,j),dp[i][j-1][1]+cal(j-1,j,i-1,j));
        }//c为初始地点

一交，哎呀30分...好尴尬呀

于是我开始思考（其实在看其他人的题解）