「洛谷P1220」关路灯

「洛谷P1220」关路灯 - 搜索

本文主要是介绍「洛谷P1220」关路灯 - 搜索，希望对大家解决编程问题提供一定的参考价值，需要的开发者们随着小编来一起学习吧！

题目描述

某一村庄在一条路线上安装了n盏路灯，每盏灯的功率有大有小（即同一段时间内消耗的电量有多有少）。老张就住在这条路中间某一路灯旁，他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。
为了给村里节省电费，老张记录下了每盏路灯的位置和功率，他每次关灯时也都是尽快地去关，但是老张不知道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯，然后可以向左也可以向右去关灯。开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率，然后选择先关掉功率大的一边，再回过头来关掉另一边的路灯，而事实并非如此，因为在关的过程中适当地调头有可能会更省一些。
现在已知老张走的速度为1m/s，每个路灯的位置（是一个整数，即距路线起点的距离，单位：m）、功率（W），老张关灯所用的时间很短而可以忽略不计。
请你为老张编一程序来安排关灯的顺序，使从老张开始关灯时刻算起所有灯消耗电最少（灯关掉后便不再消耗电了）。

输入输出格式

输入格式

输入文件第一行是两个数字n和c，n表示路灯的总数，c老张所处位置的路灯号；
接下来n行，每行两个数据，给出每盏路灯的位置和功率。

输出格式

一个数据，即最少的功耗(单位：J，1J＝1W·s)。

输入输出样例

输入样例

5 3
2 10
3 20
5 20
6 30
8 10

输出样例

270

样例解释

此时关灯顺序为3 4 2 1 5，不必输出这个关灯顺序

分析

搜索题。定义 $d f s (x, n o w)$ 指当前在 $x$ 号灯，已经耗电 $n o w (J)$ ，这样就很好搜索了。不过注意一点，每次找只需要找当前节点 $x$ 的左右两边就行了，这里运用的贪心的思想，就是如果去关 $x$ 的非相邻的灯，一定会经过其中一个相邻的灯，这样倒不如先关那个相邻的灯，使功耗更少，这样就可以过了。其实，代码中 $d f s$ 函数里的循环还可以省掉，不过这样已经够了。

当然，此题Dp可做。定义 $f [i] [j] [0]$ 为关掉 $[i, j]$ 区间的灯，最后在 $i$ 处， $f [i] [j] [1]$ 表示关掉 $[i, j]$ 区间的灯，最后在 $j$ 处。则

$f[i][j][0]=\min \{f[i+1][j][0]+(sum[n]-(sum[j]-sum[i]))\times(a[i+1]-a[i]),\\f[i+1][j][1]+(sum[n]-(sum[j]-sum[i]))\times(a[j]-a[i])) \}$

$f[i][j][1]=\min \{ f[i][j-1][0]+(sum[n]-(sum[j-1]-sum[i-1]))\times(a[j]-a[i]),\\f[i][j-1][1]+(sum[n]-(sum[j-1]-sum[i-1]))\times(a[j]-a[j-1]) \}$

其中， $a [i]$ 指第 $i$ 盏路灯的位置， $s u m [i]$ 指区间 $[1, i]$ 的功率和，即 $s u m [i] = s u m [i - 1] +$ 第 $i$ 盏灯的功率。

还要注意初始化，一开始将 $f [] [] []$ 数组归为 $+\infty$ ，将 $f [c] [c] [0] = f [c] [c] [1] = 0$ , $c$ 指一开始的位置，外层 $j$ 从 $c$ 到 $n$ ，内层 $i$ 从 $j + 1$ 到 $1$ ，依次更新即可。

代码

#include <iostream>
#include <cstdio>
#include <cmath>
using namespace std;
struct node {int power;//耗电量int pos;//位置
}a[55];
int ans=0x7fffffff/2,n,c;
int vis[55];//标记有没有走过
void dfs(int x,int now) {int t=0;if (now>ans) return;//当前耗电量已经大于最优解,直接returnint i=x+1;while (vis[i]&&i<=n) i++;//找右边if (i<=n){t=0;for (int j=1;j<=n;j++) {//这层以及下层循环可以省掉if (!vis[j]) t+=abs(a[x].pos-a[i].pos)*a[j].power;}vis[i]=1;dfs(i,now+t);vis[i]=0;}i=x-1;while (vis[i]&&i>=1) i--;//找左边if (i>=1) {t=0;for (int j=1;j<=n;j++) {if (!vis[j]) t+=abs(a[x].pos-a[i].pos)*a[j].power;}vis[i]=1;dfs(i,now+t);vis[i]=0;}if (t==0) ans=min(ans,now);//没有可找的,说明已经把灯关完了,更新最优值
}
int main() {scanf("%d%d",&n,&c);for (int i=1;i<=n;i++)scanf("%d%d",&a[i].pos,&a[i].power);vis[c]=1;dfs(c,0);printf("%d",ans);return 0;
}