P1220 关路灯

XichenOC · 2024-11-15 11:08:29 · 题解

P1220 关路灯

题目翻译：

给定一段路，路上每个灯的位置，和每个灯的功率。并给出老张的初始位置，求出一个方案，使得老张关完所有灯时所消耗的电量最小，并输出最小电量

思路：

只是一道很明显的区间dp，有与每关完一个区间内的灯时，老张可嫩在这个区间的左边或右边，那我令dp[i][j][op],表示关完i,j这一区间的等后，老张在op边时的最小耗电量。当op=0时表示在左边，op=1时表示在右边。接下来分类思考：

>$(1)$直接从$i+1,j$左边转移到$i,j$，也就时不转弯，那么耗电量为 >$$$dp[i][j][0]=dp[i+1][j][0]+(p[i+1]-p[i])*cost$$$ >其中$p[i]$表示第$i$个灯的距离，$cost$表示剩余路灯消耗功率。 >$(2)$若它上个区间结束与右边的话，那就要转弯，则耗电量为 >$$$dp[i][j][0]=dp[i+1][j][1]+(p[j]-p[i]) \times cost$$$ 那当前状态的动态转移方程为其两值求最小，则为： $$$dp[i][j][0]=min(dp[i+1][j][0]+(p[i+1]-p[i]) \times cost,dp[i+1][j][1]+(p[j]-p[i]) \times cost)$$$ 若我们提前运用前缀和，预处理了$use[i][j]$，表示已经关完$i,j$的灯之后的每秒耗电量，那转移方程可以变为： $$$dp[i][j][0]=min(dp[i+1][j][0]+(p[i+1]-p[i]) \times use[i+1][j],dp[i+1][j][1]+(p[j]-p[i]) \times use[i+1][j])$$$ --- 同理可得若要到右边，则： $$$dp[i][j][1]=min(dp[i][j-1][1]+(p[j]-p[j-1]) \times use[i][j-1],dp[i][j-1][0]+(p[j]-p[i]) \times use[i][j-1])$$$ 及把顺序调换一遍即可 # 实现： $1.$只需要先维护一前缀和$sum[i]$在循环求出$use[i][j]$（**注意**：要给$dp$初始化到最大，并把$dp[c][c][0]$和$dp[c][c][1]$初始化为零，因为老张开局就会关掉）

memset(dp,0x3f,sizeof(dp));
for(int i=1;i<=n;i++){
    cin>>p[i]>>w[i];
    sum[i]=sum[i-1]+w[i];
}
for(int i=1;i<=n;i++){
    for(int j=1;j<=n;j++){
        use[i][j]=sum[n]-sum[j]+sum[i-1];
    }
}
dp[c][c][0]=dp[c][c][1]=0;