Obviously,the answer to going to the $i$-th floor can be calced by defining the following DP table:↵
↵
- $f[i][0]$ = The answer if we go from $i-1$-th floor to $i$-th floor by stairs.↵
- $f[i][1]$ = The answer if we go from $i-1$-th floow to $i$-th floor by elevator.↵
↵
And we can calc $f[i][0/1]$ by $f[i-1][0/1]$,through the following equations:↵
↵
- $f[i][0] = \min(f[i-1][0],f[i-1][1]) + a_i $↵
- $f[i][1] = \min(f[i-1][0]+c,f[i-1][1]) + b_i $,because if we walk to the $i-1$-th floor,we must wait for elevator,but if we go to $i-1$-th floor by elevator,we don't need to wait again.↵
↵
So this problem can be solved in a total of $O(n)$ time.This is the code:↵
↵
```cpp↵
#include<iostream>↵
#include<cstdio>↵
#include<cstring>↵
#include<string>↵
using namespace std;↵
↵
const int CN = 2e5+5;↵
↵
int n,c,a[CN],b[CN],f[2][CN];↵
↵
int main()↵
{↵
scanf("%d%d",&n,&c);↵
for(int i=2;i<=n;i++) scanf("%d",&a[i]);↵
for(int i=2;i<=n;i++) scanf("%d",&b[i]);↵
↵
f[0][1] = 0; f[1][1] = c; // if we ↵
for(int i=2;i<=n;i++){↵
f[0][i] = min(f[0][i-1], f[1][i-1]) + a[i];↵
f[1][i] = min(f[0][i-1] + c, f[1][i-1]) + b[i];↵
}↵
↵
for(int i=1;i<=n;i++) printf("%d ",min(f[0][i], f[1][i]));↵
↵
return 0;↵
}↵
``` ↵
↵
- $f[i][0]$ = The answer if we go from $i-1$-th floor to $i$-th floor by stairs.↵
- $f[i][1]$ = The answer if we go from $i-1$-th floow to $i$-th floor by elevator.↵
↵
And we can calc $f[i][0/1]$ by $f[i-1][0/1]$,through the following equations:↵
↵
- $f[i][0] = \min(f[i-1][0],f[i-1][1]) + a_i $↵
- $f[i][1] = \min(f[i-1][0]+c,f[i-1][1]) + b_i $,because if we walk to the $i-1$-th floor,we must wait for elevator,but if we go to $i-1$-th floor by elevator,we don't need to wait again.↵
↵
So this problem can be solved in a total of $O(n)$ time.This is the code:↵
↵
```cpp↵
#include<iostream>↵
#include<cstdio>↵
#include<cstring>↵
#include<string>↵
using namespace std;↵
↵
const int CN = 2e5+5;↵
↵
int n,c,a[CN],b[CN],f[2][CN];↵
↵
int main()↵
{↵
scanf("%d%d",&n,&c);↵
for(int i=2;i<=n;i++) scanf("%d",&a[i]);↵
for(int i=2;i<=n;i++) scanf("%d",&b[i]);↵
↵
f[0][1] = 0; f[1][1] = c; // if we ↵
for(int i=2;i<=n;i++){↵
f[0][i] = min(f[0][i-1], f[1][i-1]) + a[i];↵
f[1][i] = min(f[0][i-1] + c, f[1][i-1]) + b[i];↵
}↵
↵
for(int i=1;i<=n;i++) printf("%d ",min(f[0][i], f[1][i]));↵
↵
return 0;↵
}↵
``` ↵
