建议
【答疑】P1220 关路灯
YIZHIYANG 一只羊 LV 8 SU @ 2025-7-21 23:06:17

P1220 关路灯

题目描述

某一村庄在一条路线上安装了 $n$ 盏路灯，每盏灯的功率有大有小（即同一段时间内消耗的电量有多有少）。老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。

为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关，但是老张不知道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯，然后可以向左也可以向右去关灯。开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率，然后选择先关掉功率大的一边，再回过头来关掉另一边的路灯，而事实并非如此，因为在关的过程中适当地调头有可能会更省一些。

现在已知老张走的速度为 $1m/s$ ，每个路灯的位置（是一个整数，即距路线起点的距离，单位： $m$ ）、功率（ $W$ ），老张关灯所用的时间很短而可以忽略不计。

请你为老张编一程序来安排关灯的顺序，使从老张开始关灯时刻算起所有灯消耗电最少（灯关掉后便不再消耗电了）。

输入格式

第一行是两个数字 $n$ （表示路灯的总数）和 $c$ （老张所处位置的路灯号）；

接下来 $n$ 行，每行两个数据，表示第 $1$ 盏到第 $n$ 盏路灯的位置和功率。数据保证路灯位置单调递增。

输出格式

一个数据，即最少的功耗（单位： $J$ ， $1J=1W\times s$ ）。

输入输出样例 #1

输入 #1

输出 #1

说明/提示

样例解释

此时关灯顺序为 3 4 2 1 5。

数据范围

$1\le n\le50$ ， $1\le c\le n$ ， $1\le W_i \le 100$ 。

分析过程

问题描述

在一条直线上有 $n$ 盏灯，每盏灯有其位置 $p_i$ 和单位时间的功率 $w_i$ 。你从第 $c$ 盏灯的位置开始，每次可以向左或向右移动去关掉一盏尚未关闭的灯。你的移动速度为 1 单位距离/单位时间。在移动过程中，所有还亮着的灯都会消耗电量。总耗电量 = $\sum (\text{某次移动花费的时间} \times \text{该时段所有亮灯的总功率})$ 。

求关掉所有灯的最小总耗电量。

核心思路与状态定义

关键性质：在任意时刻，已经关闭的灯总是形成一个连续的区间。因为如果你在区间 [i, j] 之外去关一盏更远的灯，而不关 i 或 j，这必然不是最优解（路程更长，耗电更多）。

因此，我们可以用一个区间 [i, j] 来描述“所有在 i 和 j 之间的灯（包括端点）都已关闭”的状态。

状态定义：由于下一次决策的成本与当前所在的位置有关，仅有区间 [i, j] 是不够的。我们需要一个维度来表示当前是停在区间的左端点还是右端点。

dp[i][j][0]: 表示关掉区间 [i, j] 内所有灯，且最后停在左端点 i 时的最小总耗电量。
dp[i][j][1]: 表示关掉区间 [i, j] 内所有灯，且最后停在右端点 j 时的最小总耗电量。

状态转移

我们从小区间向大区间进行扩展。

计算 dp[i][j][0] (目标是停在 i)
- 要关掉 [i, j] 区间并停在 i，那么最后一步一定是关掉第 i 盏灯。
- 这意味着上一个状态是 [i+1, j] 区间的灯已全被关掉。
- 此时，人可能停在 i+1 (来自 dp[i+1][j][0]) 或 j (来自 dp[i+1][j][1])。
- 从 i+1 移动到 i: 耗时 p[i+1] - p[i]。
- 从 j 移动到 i: 耗时 p[j] - p[i]。
- 在移动过程中，所有未被关掉的灯（即 [1, i] 和 [j+1, n] 区间的灯）都在耗电。其总功率为 (s[n] - s[j]) + s[i]。
- 转移方程：
  $$dp[i][j][0] = \min \begin{cases} dp[i+1][j][0] + (p_{i+1} - p_i) \times (\sum_{k=1}^i w_k + \sum_{k=j+1}^n w_k) \\ dp[i+1][j][1] + (p_j - p_i) \times (\sum_{k=1}^i w_k + \sum_{k=j+1}^n w_k) \end{cases} $$
计算 dp[i][j][1] (目标是停在 j)
- 同理，最后一步一定是关掉第 j 盏灯，上一个状态是 [i, j-1] 区间已关闭。
- 人可能停在 i (来自 dp[i][j-1][0]) 或 j-1 (来自 dp[i][j-1][1])。
- 此时亮着的灯是 [1, i-1] 和 [j, n]。总功率为 s[i-1] + (s[n] - s[j-1])。
- 转移方程：
  $$dp[i][j][1] = \min \begin{cases} dp[i][j-1][0] + (p_j - p_i) \times (\sum_{k=1}^{i-1} w_k + \sum_{k=j}^n w_k) \\ dp[i][j-1][1] + (p_j - p_{j-1}) \times (\sum_{k=1}^{i-1} w_k + \sum_{k=j}^n w_k) \end{cases} $$

优化：为了快速计算区间外灯的总功率，我们可以预处理功率的前缀和数组 s。

初始状态: dp[c][c][0] = dp[c][c][1] = 0，因为开始时就在第 c 盏灯处，关掉它不产生任何消耗。

最终答案: min(dp[1][n][0], dp[1][n][1])。

参考代码一 (自底向上 DP)

这种写法直接使用循环，从小到大枚举区间长度 l，再枚举区间的起始点 i，逐步填充 dp 数组。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int n, c;
int p[55], w[55];
int s[55];
ll dp[55][55][2];

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> c;

    for (int i = 1; i <= n; ++i) {
        cin >> p[i] >> w[i];
        s[i] = s[i - 1] + w[i];
    }

    memset(dp, 0x3f, sizeof(dp));
    dp[c][c][0] = dp[c][c][1] = 0;

    for (int l = 2; l <= n; ++l) { // l是区间长度
        for (int i = 1; i <= n - l + 1; ++i) {
            int j = i + l - 1;

            // 在[i,j]区间，要计算停在i点的最小代价
            // 必然是从[i+1,j]区间转移而来，之前停在i+1或j
            ll pw = s[i] + s[n] - s[j]; // 此时还亮着的灯的总功率
            dp[i][j][0] = min(dp[i + 1][j][0] + (ll)(p[i + 1] - p[i]) * pw,
                            dp[i + 1][j][1] + (ll)(p[j] - p[i]) * pw);
            
            // 计算停在j点的最小代价
            // 必然是从[i,j-1]区间转移而来，之前停在i或j-1
            pw = s[i - 1] + s[n] - s[j - 1]; // 此时还亮着的灯的总功率
            dp[i][j][1] = min(dp[i][j - 1][0] + (ll)(p[j] - p[i]) * pw,
                            dp[i][j - 1][1] + (ll)(p[j] - p[j - 1]) * pw);
        }
    }

    cout << min(dp[1][n][0], dp[1][n][1]) << endl;

    return 0;
}

参考代码二 (记忆化搜索)

这种写法使用递归函数实现，逻辑与 DP 完全一致，但思考方式是“从当前状态出发，走向下一个状态的成本是多少”。

状态定义: go(i, j, k) 表示已经关掉了 [i, j] 区间的灯，当前停在 k (0代表左端点i, 1代表右端点j) 位置，要关掉剩下所有灯所需的最小未来耗电量。

转移逻辑: 从状态 (i, j, k)，有两个决策：

向左走，去关掉 i-1 号灯。
向右走，去关掉 j+1 号灯。

计算出这两个决策的成本（移动成本 + 递归调用得到的未来成本），取较小者。

递归出口: 当 i=1 且 j=n 时，所有灯都已关闭，未来成本为0，递归结束。

#include <bits/stdc++.h>

using namespace std;
using ll = long long;

int n, c;
int p[55], w[55];
int s[55];
ll mem[55][55][2];

ll go(int i, int j, int k) {
    if (i == 1 && j == n) { // 所有灯都已关闭，递归结束
        return 0;
    }
    if (mem[i][j][k] != -1) { // 如果已经计算过，直接返回
        return mem[i][j][k];
    }

    ll res = 2e18; // 初始化为极大值
    ll pw = s[i - 1] + (s[n] - s[j]); // 计算当前还亮着的灯的总功率

    // 决策1：向左走，去关掉 i-1 号灯
    if (i > 1) {
        ll cost;
        if (k == 0) { // 当前在左端点i
            cost = (ll)(p[i] - p[i - 1]) * pw;
        } else { // 当前在右端点j
            cost = (ll)(p[j] - p[i - 1]) * pw;
        }
        res = min(res, cost + go(i - 1, j, 0));
    }

    // 决策2：向右走，去关掉 j+1 号灯
    if (j < n) {
        ll cost;
        if (k == 0) { // 当前在左端点i
            cost = (ll)(p[j + 1] - p[i]) * pw;
        } else { // 当前在右端点j
            cost = (ll)(p[j + 1] - p[j]) * pw;
        }
        res = min(res, cost + go(i, j + 1, 1));
    }

    return mem[i][j][k] = res; // 记忆化并返回结果
}

int main() {
    ios::sync_with_stdio(0);
    cin.tie(0);
    cout.tie(0);

    cin >> n >> c;

    for (int i = 1; i <= n; ++i) {
        cin >> p[i] >> w[i];
        s[i] = s[i - 1] + w[i];
    }
    
    memset(mem, -1, sizeof(mem));

    // 初始状态：只关了c号灯，人就在c的位置
    // 此时[c,c]区间的左端点和右端点是同一个，所以k=0或k=1都行
    cout << go(c, c, 0) << endl;

    return 0;
}

问题代码

#include <bits/stdc++.h>

#define N 102

using namespace std;

int n, c;

int pos[N], w[N], sum[N], f[N][N][2];

int cal(int i, int j) { return (pos[j] - pos[i]) * (sum[j] - sum[i - 1]); }

signed main() {
  cin >> n >> c;

  for (int i = 1; i <= n; i++) {
    cin >> pos[i] >> w[i];

    sum[i] = sum[i - 1] + w[i];
  }

  memset(f, 0x3f, sizeof(f));

  f[c][c][0] = f[c][c][1] = 0;

  for (int l = 2; l <= n; l++) {
    for (int i = 1, j = i + l - 1; j <= n; j++, i++) {
      f[i][j][0] = min(f[i + 1][j][0] + cal(i, i + 1),
                       f[i + 1][j][1] + cal(i, j) + cal(i + 1, j));

      f[i][j][1] = min(f[i][j - 1][0] + cal(j - 1, j),
                       f[i][j - 1][1] + cal(i, j) + cal(i, j - 1));
    }
  }

  cout << min(f[1][n][0], f[1][n][1]) << "\n";

  return 0;
  }

// Problem: P1220 关路灯
// Contest: Luogu
// URL: https://www.luogu.com.cn/problem/P1220
// Memory Limit: 512 MB
// Time Limit: 1000 ms
// byyyyyyyyy YZY

#include<bits/stdc++.h> 
#define N 102 
using namespace std; 
int n,c; 

long long pos[N],w[N],sum[N],f[N][N][2]; 

signed main() { 
	cin>>n>>c; 
	for(int i = 1;i <= n;i ++) { 
		cin>>pos[i]>>w[i]; 
		sum[i] = sum[i - 1] + w[i]; 
	} 
	memset(f,0x3f,sizeof(f)); 
	f[c][c][0] = f[c][c][1] = 0; 
	for(int l = 2;l <= n;l ++) { 
		for(int i = 1,j = i + l - 1;j <= n;j ++,i ++) { 
            // 状态转移的代价计算是 (走过的时间) * (这个时间段内还在亮着的灯的总功率)
            // 当我们处理完区间 [i+1, j]，要去关第 i 盏灯时，还在亮的灯是 [1, i] 和 [j+1, n]
			long long rm = (sum[i]) + (sum[n] - sum[j]);
			f[i][j][0] = min(f[i + 1][j][0] + (pos[i + 1] - pos[i]) * rm, 
                             f[i + 1][j][1] + (pos[j] - pos[i]) * rm); 

            // 当我们处理完区间 [i, j-1]，要去关第 j 盏灯时，还在亮的灯是 [1, i-1] 和 [j, n]
			long long rl = (sum[i - 1]) + (sum[n] - sum[j-1]);
			f[i][j][1] = min(f[i][j - 1][0] + (pos[j] - pos[i]) * rl, 
                             f[i][j - 1][1] + (pos[j] - pos[j - 1]) * rl); 
		} 
	} 
	cout<<min(f[1][n][0],f[1][n][1])<<"\n"; 
	return 0; 
}

过掉了

#include<bits/stdc++.h>
#define N 102
using namespace std;
int n,c;
int a[N],w[N],sum[N];
int  f[N][N][2];
signed main() {
	cin>>n>>c;
	for(int i = 1;i <= n;i ++) {
		cin>>a[i]>>w[i];
		sum[i] = sum[i - 1] + w[i];
	}
	memset(f,0x3f,sizeof(f));
	f[c][c][0] = f[c][c][1] = 0;
	for(int l = 2;l <= n;l ++) {
		for(int i = 1,j = i + l - 1;j <= n;j ++,i ++) {
			int t = sum[n] + sum[i] - sum[j];
			f[i][j][0] = min(f[i + 1][j][0] + (a[i + 1] - a[i]) * t,f[i + 1][j][1] + (a[j] - a[i]) * t);
			t = sum[n] + sum[i - 1] - sum[j - 1];
			f[i][j][1] = min(f[i][j - 1][0] + (a[j] - a[i]) * t,f[i][j - 1][1] + (a[j] - a[j - 1]) * t);
		}
	}
	cout<<min(f[1][n][0],f[1][n][1])<<"\n";
	return 0;
}

目前还没有评论...

【答疑】P1220 关路灯