题解 P1220 【关路灯 】
panda_2134
2017-08-14 16:08:16
很类似lrj的紫书《算法竞赛入门经典》上面一个题目（P293）
首先我们发现当前时刻已经关闭的灯在一个连续区间里面最划算。这很显然：如果a和b是不连续的两盏灯，被灯c分开，那么我关了a再去关b的时候完全可以顺带把c关掉，答案只会更好。然后我们发现在关闭了一个连续的区间的灯之后，人一定在端点。
于是就可以dp了，设$f(i,j,k)$为已经关闭了区间$[i,j]$里面的灯时的最小耗电量，k=0表示人在区间左端点，k=1表示人在区间右端点。
于是$f(i,j,0)$就可以从$f(i+1,j,0/1)$转移而来。考虑从i+1或者j走到点i的路程中，还开着的灯的耗电即可。详见代码。
```cpp
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <algorithm>
using namespace std;
const int MAXN=50;
int N,C,P[MAXN+10],W[MAXN+10],Sum[MAXN+10],opt[MAXN+10][MAXN+10][3];
int main(){
scanf("%d%d",&N,&C);
for(int i=1;i<=N;i++) {
scanf("%d%d",&P[i],&W[i]);
Sum[i]=Sum[i-1]+W[i];
}
for(int i=1;i<=N;i++)
opt[i][i][0]=opt[i][i][1]=Sum[N]*abs(P[i]-P[C]);
for(int len=2;len<=N;len++)
for(int i=1;i<=N-len+1;i++) {
int j=i+len-1;
opt[i][j][0]=min(
opt[i+1][j][0]+abs(P[i+1]-P[i])*(Sum[i]+Sum[N]-Sum[j]),
opt[i+1][j][1]+abs(P[j]-P[i])*(Sum[i]+Sum[N]-Sum[j])
);
opt[i][j][1]=min(
opt[i][j-1][0]+abs(P[i]-P[j])*(Sum[i-1]+Sum[N]-Sum[j-1]),
opt[i][j-1][1]+abs(P[j]-P[j-1])*(Sum[i-1]+Sum[N]-Sum[j-1])
);
}
printf("%d",min(opt[1][N][0],opt[1][N][1]));
return 0;
}
```