题面

You are planning to buy an apartment in a n-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:

ai for all i from 1 to n−1 be the time required to go from the i-th floor to the (i+1)-th one (and from the (i+1)-th to the i-th as well) using the stairs;
bi for all i from 1 to n−1 be the time required to go from the i-th floor to the (i+1)-th one (and from the (i+1)-th to the i-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 x to any floor y (x≠y) in two different ways:

If you are using the stairs, just sum up the corresponding values of ai. Formally, it will take ∑i=min(x,y)max(x,y)−1ai time units.
If you are using the elevator, just sum up c and the corresponding values of bi. Formally, it will take c+∑i=min(x,y)max(x,y)−1bi time units.
You can perform as many moves as you want (possibly zero).

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

Input
The first line of the input contains two integers n and c (2≤n≤2⋅105,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 ai is the time required to go from the i-th floor to the (i+1)-th one (and from the (i+1)-th to the i-th as well) using the stairs.

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

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

中文

您打算在n楼建筑中购买公寓。楼层从底部到顶部从1到n编号。首先，对于每个楼层，您想知道从第一层（最底层）到达该层的最短总时间。
让：
从1到n-1的所有i的ai是从第i层到第（i + 1）个（以及从第（i + 1）到第i个）所需的时间）使用楼梯；
从1到n-1的所有i的bi是从第i层到第（i + 1）个（以及从第（i + 1）到第i个）所需的时间）使用电梯，还有一个值c –电梯使用的时间开销（您需要等待，电梯门太慢！）。
一步之遥，您可以用两种不同的方式从停留在x处的楼层移动到任何楼层y（x≠y）：

如果您正在使用楼梯，只需将ai的相应值相加即可。形式上，它将采用∑i = min（x，y）max（x，y）-1ai时间单位。
如果使用电梯，只需将c和bi的对应值相加即可。形式上，它将采用c + ∑i = min（x，y）max（x，y）-1bi个时间单位。
您可以执行任意数量的移动（可能为零）。

因此，您的任务是为每个i确定从第1层（底部）到达第i层所需的最短总时间。

输入
输入的第一行包含两个整数n和c（2≤n≤2⋅105,1≤c≤1000）-建筑物中的楼层数和电梯行驶的时间开销。

输入的第二行包含n-1个整数a1，a2，…，an-1（1≤ai≤1000），其中ai是从第i层到（i + 1）-所需的时间。第一个（也从第（i + 1）到第i个）。

输入的第三行包含n-1个整数b1，b2，...，bn-1（1≤bi≤1000），其中bi是从第i层到（i + 1）-所需的时间。第一个（也从第（i + 1）到第i个）。

输出
打印n个整数t1，t2，…，tn，其中ti是从一楼到达第i楼的最小总时间，如果您可以执行任意数量的移动。

样例输入

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

样例输出

0 7 13 18 24 35 36 37 40 45

题意

n层楼，a[i] (0<i<n)表示从 i 楼到 i + 1 楼走楼梯的时间，b[i] (0<i<n)表示从 i 楼到 i + 1 楼乘电梯的时间，其中每一次乘电梯需要等待 k 时间，楼梯和电梯一次均可上从 x 楼上升到 y 楼 ( y != x )，即一次可以通过楼梯或电梯上升任意层数 。求从1楼到 1 ~ n 层楼所需要的最短时间

思路

dp题：二维数组dp[i][j]，表示通过 j 的方法（ j = 0 表示楼梯，j = 1表示电梯）第 i 层所需的最少时间。
所以得出状态转移方程

dp[i][0]=min(dp[i-1][0]+a[i],dp[i-1][1]+a[i]);
dp[i][1]=min(dp[i-1][1]+b[i],dp[i-1][0]+b[i]+k); 
dp[1][0]=0,dp[1][1]=1e18;

答案是

min(dp[i][0],dp[i][1]);

AC代码

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=1e9;
const int N=2e5+10;
ll n,k,a[N],b[N],dp[N][2];

int main()
{
    ios::sync_with_stdio(false);
    cin>>n>>k;
    for(int i=1;i<n;i++)
        cin>>a[i];
    for(int i=1;i<n;i++)
        cin>>b[i];
    cout<<0<<" ";
    dp[0][1]=1e18;
    for(int i=1;i<n;i++)
    {
        dp[i][0]=min(dp[i-1][0]+a[i],dp[i-1][1]+a[i]);
        dp[i][1]=min(dp[i-1][1]+b[i],dp[i-1][0]+b[i]+k);
        cout<<min(dp[i][0],dp[i][1])<<" ";
    }
    return 0;
}