### ce_amtic's blog

By ce_amtic, history, 18 months ago, Obviously,the answer to going to the $i$-th floor can be calced by defining the following DP table:

• $f[i]$ = The answer if we go from $i-1$-th floor to $i$-th floor by stairs.
• $f[i]$ = 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] = \min(f[i-1],f[i-1]) + a_i$
• $f[i] = \min(f[i-1]+c,f[i-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:

#include<iostream>
#include<cstdio>
#include<cstring>
#include<string>
using namespace std;

const int CN = 2e5+5;

int n,c,a[CN],b[CN],f[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; f = c; // if we go by elevator since the first floor,we must wait first
for(int i=2;i<=n;i++){
f[i] = min(f[i-1], f[i-1]) + a[i];
f[i] = min(f[i-1] + c, f[i-1]) + b[i];
}

for(int i=1;i<=n;i++) printf("%d ",min(f[i], f[i]));

return 0;
}  Comments (4)
 » Auto comment: topic has been updated by ce_amtic (previous revision, new revision, compare).
 » Auto comment: topic has been updated by ce_amtic (previous revision, new revision, compare).
 » How strong you are!!
 » How strong you are!!what a strong orz ft.