关路灯

标签：区间dp。

1. 状态量

设：\(f[i][j][0 / 1]\) 是在区间\([i, j]\)内老王在左端点\((0)\)和右端点\((1)\)的情况。

1. 转移方程。

由状态量定义可得，我们进行转移是，一定是从这个区间少一个路灯的区间来进行转移。于是有：

\[f[i][j][0] = min \begin{cases} \sum_{i = 1, i \not \in [i + 1, j]}^{n} P[i] \ f[i+1][j][1] + dis(i, j) * \sum_{i = 1, i \not \in [i + 1, j]}^{n} P[i] \ \end{cases}\]
\[f[i][j][1] = min \begin{cases} f[i][j - 1][1] + dis(j - 1, j) * \sum_{i = 1, i \not \in [i, j - 1]}^{n} P[i] \ f[i+1][j][1] + dis(i, j) * \sum_{i = 1, i \not \in [i, j - 1]}^{n} P[i] \ \end{cases}\]

1. 特别注意

(1)当且仅当，$ i <= c ?and ?c <= j $时， 可以转移， 不然就是inf。
至于为什么，自己脑补一下老王行走时的画面(瞬移)

(2)关于我一开始做这道题时没有过来的点。

-> f[b][e][0] sum[n] - sum[e] + sum[b]
-> f[b][e][1] sum[n] - sum[e - 1] + sum[b - 1]

后来想了一下， 是因为在转移的过程中，i， 或j端同样在耗能。

1. 代码

#include<bits/stdc++.h>
using namespace std;
const int maxn = 100 + 5;
int n, c;
int p[maxn], w[maxn], sum[maxn];
int f[maxn][maxn][2]; 
int main(){
    cin >> n >> c;
    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 b = 1, e; (e = b + i - 1) <= n;b ++){
            if(b <= c && e >= c){
                f[b][e][0] = min (
                    f[b + 1][e][0] + (p[b + 1] - p[b]) * (sum[n] - sum[e] + sum[b]),
                    f[b + 1][e][1] + (p[e] - p[b]) * (sum[n] - sum[e] + sum[b])
                );
                f[b][e][1] = min (
                    f[b][e - 1][1] + (p[e] - p[e - 1]) * (sum[n] - sum[e - 1] + sum[b - 1]),
                    f[b][e - 1][0] + (p[e] - p[b]) * (sum[n] - sum[e - 1] + sum[b - 1]) 
                );
            } else {
                f[b][e][0] = f[b][e][1] = 1e9;
            }
        }
    }
    cout << min(f[1][n][0], f[1][n][1]) << endl;
    return 0;
} 

BLOG观看

关路灯

原文：https://www.cnblogs.com/yangxuejian/p/11785328.html