洛谷 P1220 关路灯 题解

发表于 | 分类于 | | 热度: ℃

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 <iostream>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;

const int N = 60;
struct light
{
    int pos, w;
} a[N];
int n, c, sum[N], f[N][N][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;
}