題意

n層樓，a[i] (0<i<n)表示從 i 樓到 i + 1 樓走樓梯的時間，b[i] (0<i<n)表示從 i 樓到 i + 1 樓乘電梯的時間，其中每一次乘電梯需要等待 k 時間，樓梯和電梯一次均可上從 x 樓上升到 y 樓 ( y != x )，即一次可以通過樓梯或電梯上升任意層數(shù) 。求從1樓到 1 ~ n 層樓所需要的最短時間

題目

You are planning to buy an apartment in a nn-floor building. The floors are numbered from 1 to n from the bottom to the top. At first for each floor you want to know the minimum total time to reach it from the first (the bottom) floor.

Let:

aiai for all ii from 1 to n?1 be the time required to go from the ii-th floor to the (i+1)-th one (and from the (i+1)-th to the i-th as well) using the stairs;
bibi for all ii from 11 to n?1n?1 be the time required to go from the ii-th floor to the (i+1)-th one (and from the(i+1)-th to the ii-th as well) using the elevator, also there is a value c — time overhead for elevator usage (you need to wait for it, the elevator doors are too slow!).
In one move, you can go from the floor you are staying at xx to any floor yy (x≠y) in two different ways:

If you are using the stairs, just sum up the corresponding values of aiai. Formally, it will take $$\sum _{min(x,y)}^{max(x,y)?1}ai$$ time units.
If you are using the elevator, just sum up cc and the corresponding values of bibi. Formally, it will take c+$$\sum _{min(x,y)}^{max(x,y)?1}bi$$ time units.
You can perform as many moves as you want (possibly zero).
?
ai

So your task is for each ii to determine the minimum total time it takes to reach the ii-th floor from the 1-st (bottom) floor.

Input

The first line of the input contains two integers n and c (2≤n≤2?$10^5$,1≤c≤1000) — the number of floors in the building and the time overhead for the elevator rides.

The second line of the input contains n?1 integers a1,a2,…,an?1 (1≤ai≤1000), where aiai is the time required to go from the ii-th floor to the (i+1)-th one (and from the(i+1)-th to the ii-th as well) using the stairs.

The third line of the input contains n?1n?1 integers b1,b2,…,bn?1 (1≤bi≤1000), where bibi is the time required to go from the ii-th floor to the (i+1)-th one (and from the (i+1)-th to the ii-th as well) using the elevator.

Output

Print nn integers t1,t2,…,tn where titi is the minimum total time to reach the ii-th floor from the first floor if you can perform as many moves as you want.

Examples

Input

10 2
7 6 18 6 16 18 1 17 17
6 9 3 10 9 1 10 1 5

Output

0 7 13 18 24 35 36 37 40 45

Input

10 1
3 2 3 1 3 3 1 4 1
1 2 3 4 4 1 2 1 3

Output

0 2 4 7 8 11 13 14 16 17

官方題解

This is easy dynamic programming problem. It is easy to understand that we don’t need to go down at all (otherwise your solution will be Dijkstra’s algorithm, not dynamic programming). Let dpi,0be the minimum required time to reach the floor ii if we not in the elevator right now and dpi,1 be the minimum required time to reach the floor ii if we in the elevator right now.

Initially, all values dp are +∞, except dp1,0=0 and dp1,1=c.

Transitions are pretty easy:

dpi+1,0=min(dpi+1,0,dpi,0+ai) (we was not in the elevator and going to the next floor using stairs);
dpi+1,0=min(dpi+1,0,dpi,1+ai) (we was in the elevator and going to the next floor using stairs);
dpi+1,1=min(dpi+1,1,dpi,0+bi+c) (we was not in the elevator and going to the next floor using elevator);
dpi+1,1=min(dpi+1,1,dpi,1+bi) (we was in the elevator and going to the next floor using elevator).
The answer for the ii-th floor is min(dpi,0,dpi,1).

Time complexity: O(n).

百度翻譯

這是一個簡單的動態(tài)規(guī)劃問題。很容易理解，我們根本不需要往下走（否則你的解決方案將是Dijkstra的算法，而不是動態(tài)編程）如果我們現(xiàn)在不在電梯里，dpi，0是到達二層的最小要求時間；如果我們現(xiàn)在在電梯里，dpi，1是到達二層的最小要求時間。
最初，除dp1,0=0和dp1,1=c外，所有值dp均為+∞。
轉(zhuǎn)換非常容易：
dpi+1,0=min（dpi+1,0，dpi，0+ai）（我們當(dāng)時不在電梯里，正在下一層樓梯上）；
dpi+1,0=min（dpi+1,0，dpi，1+ai）（我們當(dāng)時在電梯里，正在下一層樓梯上）；
dpi+1,1=min（dpi+1,1，dpi，0+bi+c）（我們不在電梯里，乘電梯去下一層）；
dpi+1,1=min（dpi+1,1，dpi，1+bi）（我們在電梯里，乘電梯去了下一層）。
第二層的答案是min（dpi，0，dpi，1）。
時間復(fù)雜度：O（n）。

思路

dp題：二維數(shù)組dp[i][j]，表示通過 j 的方法（ j = 0 表示樓梯，j = 1表示電梯）第 i 層所需的最少時間。
可以看出有四種狀態(tài)，
樓梯——》樓梯
樓梯——》電梯
電梯——》電梯
電梯——》樓梯
所以得出狀態(tài)轉(zhuǎn)移方程
dp[i+1][0]=min(dp[i][1]+a[i],dp[i][0]+a[i]);
dp[i+1][1]=min(dp[i][1]+b[i],dp[i][0]+b[i]+c);
簡單是真簡單（理解題意，推出轉(zhuǎn)移方程），難是真的難（總會想偏，或是沒有思路）菜的摳腳??????

AC代碼

#include<cstdio> #include<cstring> #include<algorithm> using namespace std; const int N=2*1e5+10; const int inf=0x3f3f3f3f; int a[N],b[N],dp[N][2]; int n,c; int main() {while(~scanf("%d%d",&n,&c)){for(int i=1; i<n; i++)scanf("%d",&a[i]);for(int i=1; i<n; i++)scanf("%d",&b[i]);memset(dp,inf,sizeof(dp));dp[1][0]=0,dp[1][1]=c; ///dp[i][0]:走樓梯到達第i層,dp[i][1]:做電梯到達第i層for(int i=1; i<n; i++){dp[i+1][0]=min(dp[i][1]+a[i],dp[i][0]+a[i]);dp[i+1][1]=min(dp[i][1]+b[i],dp[i][0]+b[i]+c);}for(int i=1; i<=n; i++)printf("%d ",min(dp[i][0],dp[i][1]));printf("\n");}return 0; }

總結(jié)

以上是生活随笔為你收集整理的By Elevator or Stairs? CodeForces - 1249E（动态规划）的全部內(nèi)容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網(wǎng)站內(nèi)容還不錯，歡迎將生活随笔推薦給好友。