「洛谷P1220」 关路灯 题解
问题
原题链接 洛谷P1220
题目描述
某一村庄在一条路线上安装了 n 盏路灯,每盏灯的功率有大有小(即同一段时间内消耗的电量有多有少)。老张就住在这条路中间某一路灯旁,他有一项工作就是每天早上天亮时一盏一盏地关掉这些路灯。
为了给村里节省电费,老张记录下了每盏路灯的位置和功率,他每次关灯时也都是尽快地去关,但是老张不知道怎样去关灯才能够最节省电。他每天都是在天亮时首先关掉自己所处位置的路灯,然后可以向左也可以向右去关灯。开始他以为先算一下左边路灯的总功率再算一下右边路灯的总功率,然后选择先关掉功率大的一边,再回过头来关掉另一边的路灯,而事实并非如此,因为在关的过程中适当地调头有可能会更省一些。
现在已知老张走的速度为 1m/s ,每个路灯的位置(是一个整数,即距路线起点的距离,单位: m )、功率( W ),老张关灯所用的时间很短而可以忽略不计。
请你为老张编一程序来安排关灯的顺序,使从老张开始关灯时刻算起所有灯消耗电最少(灯关掉后便不再消耗电了)。
输入格式
第一行是两个数字 n (表示路灯的总数)和 c (老张所处位置的路灯号);
接下来 n 行,每行两个数据,表示第 1 盏到第 n 盏路灯的位置和功率。数据保证路灯位置单调递增。
输出格式
一个数据,即最少的功耗(单位: J,1J=1W×s ) 。
输入输出样例
#11 2 3 4 5 6
| 5 3 2 10 3 20 5 20 6 30 8 10
|
说明/提示
样例解释:
此时关灯顺序为 3 4 2 1 5。
数据范围
1≤n≤50,1≤c≤n 。
解题
从题目中可以知道,某一时刻老张只有两种选择,往左走关掉一盏灯或者往右走关掉一盏灯,并且关的灯为连续的区间,所以可以设计状态为 f[l][r][opt] 表示现在已经关掉了 [l,r] 这段区间的所有灯,现在位于 opt=0 左边,或是 opt=1 右边的最少功率。
每次转移的代价为,老张走的时间乘所有没关的灯的功率。设
gt(i,j)=m[j]−m[i]
表示获取从 i 到 j 位置所需的时间,其中 i≤j ,设
W(i,j)=w[n]−w[j]+w[i−1]
表示获取 i 与 j 这段区间以外的所有灯的总功率,其中 i≤j。
所以状态转移方程为
f[i][j][0]=min(f[i+1][j][0]+gt(i,i+1)×W(i+1,j),f[i+1][j][1])+gt(i,j)×W(i+1,j)
f[i][j][1]=min(f[i][j−1][0]+gt(i,j)×W(i,j−1),f[i][j−1][1])+gt(j−1,j)×W(i,j−1)
初始化:老张最开始所在的位置 f[c][c][0]=f[c][c][1]=0 ,其余均为无穷大。
最后答案即为 min(f[1][n][0],f[1][n][1]) 。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24
| #include<bits/stdc++.h> using namespace std; const int MAXN = 50 + 5; int n, c; int a[MAXN], s[MAXN], w[MAXN]; int f[MAXN][MAXN][2]; int main() { cin >> n >> c; for(int i = 1; i <= n; i++) cin >> a[i] >> w[i], s[i] = s[i - 1] + w[i]; memset(f, 0x3f, sizeof(f)); f[c][c][0] = f[c][c][1] = 0; for(int len = 1; len < n; len++) { for(int i = 1; i + len <= n; i++) { int j = i + len; f[i][j][0] = min(f[i + 1][j][0] + (a[i + 1] - a[i]) * (s[i] + s[n] - s[j]), f[i + 1][j][1] + (a[j] - a[i]) * (s[i] + s[n] - s[j])); f[i][j][1] = min(f[i][j - 1][0] + (a[j] - a[i]) * (s[i - 1] + s[n] - s[j - 1]), f[i][j - 1][1] + (a[j] - a[j - 1]) * (s[i - 1] + s[n] - s[j - 1])); } } cout << min(f[1][n][1], f[1][n][0]) << endl; return 0; }
|