P1220 关路灯
斯德哥尔摩
2018-10-23 21:46:04
[P1220 关路灯](https://www.luogu.org/problemnew/show/P1220)
最近疯狂沉迷普及难度$DP$。。。感觉啥都不会。。。
这一道区间$DP$题。
关灯不需要额外的时间，经过了灯就关了。
但是可能折返回去关某一个大灯会比继续往下走关接下来的一个小灯更优。
那么可以得到两种状态：沿着当前方向继续往下走，或改变方向回去关灯。
我们需要得到的整个关灯过程中的最优值，即最小耗能。
那么要设计的状态转移方程中肯定有两种方案——折返的和~~不撞南墙~~不回头的。
又因为如果想要关某一区间的灯的过程中耗能最小，所以可以转换成一个个区间来写：
去关某一区间的灯，那么整条街道上除了这一区间的灯会逐渐灭掉其他肯定会全亮。
那么我们把$dp[i][j]$记为当从$i$到$j$的灯都熄灭消耗的灯的总功率。
再进一步：
$dp[i][j][0]$表示关掉$[i,j]$的灯后，老张站在左端点$i$；
$dp[i][j][1]$表示关掉$[i,j]$的灯后,老张站在右端点$j$。
并且$dp[i][j][0]$会由两种方案推导而来：折返回来关$[i,j]$的灯，或由$i+1$深入，继续关第$i$盏灯从而扩展到$[i,j]$。
所以得到状态转移方程：
$$dp[i][j][0]=\min\left\{\begin{array}{}dp[i+1][j][0]+(pos[i+1]-pos[i])\times(sum[i]+sum[n]-sum[j])\\dp[i+1][j][1]+(pos[j]-pos[i])\times(sum[i]+sum[n]-sum[j])\end{array}\right.$$
$$dp[i][j][1]=\min\left\{\begin{array}{}dp[i][j-1][0]+(pos[j]-pos[i])\times(sum[i-1]+sum[n]-sum[j-1])\\dp[i][j-1][1]+(pos[j]-pos[j-1])\times(sum[i-1]+sum[n]-sum[j-1])\end{array}\right.$$
$pos[i]$表示第$i$个灯的位置（在程序中我直接开个结构体的），$sum[i]$表示前$i$个灯的功率总和（因为是串联嘛）。
因为最后不知道老张到底站在左端点最优还是站在右端点最优，所以在$dp[1][n][0],dp[1][n][1]$中取$\min$即为答案。
附代码：
```cpp
#include<iostream>
#include<algorithm>
#include<cstdio>
#include<cstring>
#define MAXN 60
using namespace std;
int n,s,ans;
int sum[MAXN],dp[MAXN][MAXN][2];
struct Lamp{
int pos,power;
}a[MAXN];
inline int read(){
int date=0,w=1;char c=0;
while(c<'0'||c>'9'){if(c=='-')w=-1;c=getchar();}
while(c>='0'&&c<='9'){date=date*10+c-'0';c=getchar();}
return date*w;
}
void work(){
for(int k=2;k<=n;k++)
for(int i=1;i+k-1<=n;i++){
int j=i+k-1;
dp[i][j][0]=min(dp[i+1][j][0]+(a[i+1].pos-a[i].pos)*(sum[i]+sum[n]-sum[j]),dp[i+1][j][1]+(a[j].pos-a[i].pos)*(sum[i]+sum[n]-sum[j]));
dp[i][j][1]=min(dp[i][j-1][0]+(a[j].pos-a[i].pos)*(sum[i-1]+sum[n]-sum[j-1]),dp[i][j-1][1]+(a[j].pos-a[j-1].pos)*(sum[i-1]+sum[n]-sum[j-1]));
}
ans=min(dp[1][n][0],dp[1][n][1]);
printf("%d\n",ans);
}
void init(){
n=read();s=read();
memset(dp,127,sizeof(dp));
sum[0]=dp[s][s][0]=dp[s][s][1]=0;
for(int i=1;i<=n;i++){
a[i].pos=read();a[i].power=read();
sum[i]=sum[i-1]+a[i].power;
}
}
int main(){
init();
work();
return 0;
}
```