CF1249E
By Elevator or Stairs?
题意
给你一个n层的楼房,上楼有两种方式,一种是楼梯,一种是电梯.给出数组a[i]表示i到i+1层 走楼梯所需要的时间,b[i]表示走电梯的时间,但是走电梯的情况下,进电梯和出电梯所需要的额外等待的时间是c.
- 如果使用楼梯从
x层到y层 需要 $\sum_{i=min(x,y)max(x,y)−1}^{max(x,y)−1}a_i$ 单位时间 - 如果使用电梯从
x层到y层 需要 $c+\sum_{i=min(x,y)max(x,y)−1}^{max(x,y)−1}b_i$ 单位时间 现在你在一楼,依次输出从一楼到每个楼层所需要的最短时间.
输入
$2<=n<=2e5$
$1<=c,a_i,b_i<=1e3$
思路
不难发现,永远不需要用到”下楼”这一操作 ,这个可以反证,如果从x到y(假设x小于y),需要从x->z->y来缩短路径,而且z都大于x,y的话,那么无论是楼梯还是电梯,只需要在y层停止,那么一定比折返的总时间小.
明白了这一点这个题就很简单了.
但是问题就在于c怎么处理.
我们发现,电梯可能连着上,也可能断断续续上,所以贸然在每层添加c是不合适的.
所以我们就这样定义状态:
dp[i][0]表示从1层到第i层,在i-1层使用楼梯所需要的时间.
dp[i][1]表示从1层到第i层,在i-1层使用电梯(注意,并不一定是在i-1进入的电梯,可能是在更早之前)的没出电梯的最短时间,可以理解为电梯到了,没想好下没下,这样设计是为了避免c的反复添加.
1
2
3
dp[i][0] = min(dp[i - 1][0] + a[i - 1], dp[i - 1][1] + c + a[i - 1]);
dp[i][1] = min(dp[i - 1][0] + b[i - 1], dp[i - 1][1] + b[i - 1]);
ans[i] = min(dp[i][0], dp[i][1] + c);
最后输出ans[i]即可,注意第一层不需要时间,所以dp[1][0]和dp[1][0]都是0.
AC代码
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
#include <bits/stdc++.h>
using namespace std;
#define maxn 200000 + 100
#define ll long long
int a[maxn], b[maxn];
ll dp[maxn][2];
int main() {
int n, c;
cin >> n >> c;
dp[1][0] = dp[1][1] = 0;
for (int i = 1; i <= n - 1; ++i) {
cin >> a[i];
}
for (int i = 1; i <= n - 1; ++i) {
cin >> b[i];
}
dp[2][0] = min(dp[1][0] + a[1], dp[1][1] + b[1] + c);
for (int i = 2; i <= n; ++i) {
dp[i][0] = min(dp[i - 1][0] + a[i - 1], dp[i - 1][1] + c + a[i - 1]);
dp[i][1] = min(dp[i - 1][0] + b[i - 1], dp[i - 1][1] + b[i - 1]);
}
for (int i = 1; i <= n; ++i) {
printf("%I64d ", min(dp[i][0], dp[i][1] + c));
}
printf("\n");
return 0;
}
