CF1249E By Elevator or Stairs?

题意

给定整数c和数组a，b，\(a_i\)表示通过爬楼梯的方法从第\(i\)层到\(i+1\)层需要的时间，\(b_i\)表示通过坐电梯的方法从第\(i\)层到\(i+1\)层需要的时间，坐电梯前需要等c单位时间。即对于\(i<j\)，通过爬楼梯的方法要从第\(i\)层到第\(j\)层，需要\(\sum_i^{j-1}a_i\)的时间，而坐电梯需要\(c+\sum_i^{j-1}b_i\)的时间。

解题思路

很明显的dp题，首先考虑最简单的dp思路，对于每次层枚举他是从之前的那一层转移过来的，即
\[dp_j=\min \left\{ dp_i + \sum_i^{j-1}a_i,dp_i+c+\sum_i^{j-1}b_i\right\}\]
使用前缀和的方法后式子变为
\[dp_j=\min \left\{ dp_i + sa_{j-1}-sa_i,dp_i+c+sb_{j-1}-sb_i\right\}\]
这样dp的复杂度是\(O(n^2)\)，显然会TLE，所以考虑优化一下

对于\(j\)，可以将式子中的\(sa_{j-1}\)和\(sb_{j-1}\)视为常数，那么式子变为
\[dp_j=\min \left\{ \min\left\{dp_i - sa_i\right\} + sa_{j-1},\min \left\{dp_i - sb_i \right\}+c+sb_{j-1}\right\}\]
记录\(dp_i - sa_i\)和\(dp_i - sb_i\)的最小值，每次更新即可，复杂度\(O(n)\)

AC代码

#include<bits/stdc++.h>
using namespace std;

typedef long long ll;
const int maxn=2e5+5;

int n,c,a[maxn],b[maxn];
ll dp[maxn];

int main()
{
    scanf("%d %d",&n,&c);
    for(int i=1;i<=n-1;i++)scanf("%d",&a[i]),a[i]+=a[i-1];
    for(int i=1;i<=n-1;i++)scanf("%d",&b[i]),b[i]+=b[i-1];
    ll A=0,B=0;
    printf("%lld",dp[1]);
    for(int i=1;i<=n-1;i++){
        dp[i]=min(B+b[i]+c,A+a[i]);

        A=min(A,dp[i]-a[i]);
        B=min(B,dp[i]-b[i]);

        printf(" %lld",dp[i]);
    }
    return 0;
}