题解 P1220 【关路灯 】

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的路程中,还开着的灯的耗电即可。详见代码。

#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;
}