Solution : [CF595E] By Elevator or Stairs?

Revision en2, by ce_amtic, 2019-10-29 14:42:26

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

include

include

include

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;

} ```

Tags dp

History

 
 
 
 
Revisions
 
 
  Rev. Lang. By When Δ Comment
en4 English ce_amtic 2019-10-29 14:51:22 55
en3 English ce_amtic 2019-10-29 14:47:34 2 Tiny change: 'he code:\n```cpp\n' -> 'he code:\n\n```cpp\n'
en2 English ce_amtic 2019-10-29 14:42:26 1164 (published)
en1 English ce_amtic 2019-10-29 12:49:28 199 Initial revision (saved to drafts)