Description
有 $n$ 盏路灯，每盏路灯有坐标（单位 $m$）和功率（单位 $J$）。从第 $c$ 盏路灯开始，可以向左或向右关闭路灯。速度是 $1m/s$。求所有路灯的最少耗电。输入保证坐标单调递增。
数据范围：$1<=n<=50$
Solution
设 $f[i][j][0/1]$ 为已经关闭区间 $[i,j]$ 所有灯，此时站在 左端点 $/$ 右端点 的最小耗电。
设 $d(i,j)$ 为第 $i$ 盏路灯和第 $j$ 盏路灯之间的距离，$w(i,j)$ 为 除了 $[i,j]$ 区间所有灯每秒钟的耗电总和。转移方程：
$f[i][j][0]=max(f[i+1][j][0]+d(i,i+1)w(i+1,j),f[i+1][j][1]+d(i,j)w(i+1,j))$
$f[i][j][1]=max(f[i][j-1][0]+d(i,j)w(i,j-1),f[i][j-1][1]+d(j-1,j)w(j,j-1))$
使用前缀和维护耗电之和。
Code
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
|
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
const int N = 60;
struct
{
int pos, w;
} a[N];
int n, c, sum[N], f[N][N][大专栏 洛谷 P1220 关路灯 题解s="number">2];
int main()
{
scanf("%d%d", &n, &c);
sum[0] = 0;
for(int i = 1; i <= n; i++)
{
scanf("%d%d", &a[i].pos, &a[i].w);
sum[i] = sum[i - 1] + a[i].w;
}
memset(f, 0x3f, sizeof(f));
f[c][c][0] = f[c][c][1] = 0;
for(int i = 1; i <= n; i++)
{
for(int l = 1; l + i <= n; l++)
{
int r = l + i;
int d1 = sum[n] - sum[r] + sum[l];
int d2 = sum[n] - sum[r - 1] + sum[l - 1];
if(l > c || r < c) continue;
f[l][r][0] = min(f[l][r][0], f[l + 1][r][0] + (a[l + 1].pos - a[l].pos) * d1);
f[l][r][0] = min(f[l][r][0], f[l + 1][r][1] + (a[r].pos - a[l].pos) * d1);
f[l][r][1] = min(f[l][r][1], f[l][r - 1][1] + (a[r].pos - a[r - 1].pos) * d2);
f[l][r][1] = min(f[l][r][1], f[l][r - 1][0] + (a[r].pos - a[l].pos) * d2);
}
}
printf("%d", min(f[1][n][0], f[1][n][1]));
return 0;
}
|