CF1866E题解

· · 题解

Preface

大年初一又来水题解了~~~

题目传送门

题目大意：一栋大楼有 N 层楼，三座电梯，在 Q 天里每一天 i 都有一个一座电梯运行一层楼的花费 A_i 并发生以下两个事件之一：
1.一个人从楼层 x 到楼层 y，也就是说，要有一座电梯在这一天（或之前）运行到楼层 x，再运行到楼层 y。
2.一座电梯改变运行状态，如果它之前可运行，那么从这一天开始变得不可运行，否则从这一天开始变得可运行。
你需要求出满足所有乘客要求情况下使用的最小花费。

数据范围：2\leq N\leq 10^5，1\leq Q\leq 300，1\leq A_i\leq 10^5。

Analysis

我们发现 N 很大 Q 很小，不必记录每座电梯具体的位置，只需要记录它上一次载客是在哪一次。

考虑 dp。设 f_{i,j,k} 表示三座电梯最后一次载客分别是第 i,j,k 次需要的最小花费。

我们发现，考虑第 d 次载客时，必然有一座电梯在第 d-1 次载客。枚举其它两座电梯最后一次载客的时间。

比如现在要算 f_{d,j,k}，如果第 d-1 次载客的电梯是第一座，从 f_{d-1,j,k}转移过来；否则第二座和第三座里一定有一座是上次载客的，比如它是第三座，从 f_{k,j,d-1} 转移过来。（这里的变量 k 枚举的是第一座电梯上次载客的时间）

接下来考虑如何转移。如果没有操作 2，我们要找到两次载客的间歇时间中花费最少的那一天转移，再加上从楼层 x 到楼层 y 的花费（这里我脑残预处理用了 ST 表）。加上操作二后，只需要在不可运行的时间里把这座电梯的花费设为无穷大。

时间复杂度 O(Q^3)，可以通过此题。

于是我们就做完了，只不过细节挺多的。

Code

#include<bits/stdc++.h>
#define inf (long long)1<<45
#define int long long
using namespace std;
const int _=305;
int n,q[_],d,a[4][25][_],lg[_];
void ST(int w){
    for(int i=1;(1<<i)<=q[0];i++)
        for(int j=0;j+(1<<i)-1<=q[0];j++)
            a[w][i][j]=min(a[w][i-1][j],a[w][i-1][j+(1<<i-1)]);
}
int Min(int w,int l,int r){
    int g=lg[r-l+1];
    return min(a[w][g][l],a[w][g][r-(1<<g)+1]);
}
int x[_],y[_],mp[_];
int f[_][_][_],ans;
bool f1=0,f2=0,f3=0;
变量名清晰易懂
signed main(){
    scanf("%lld%lld",&n,&q[0]);
    for(int i=0;i<4;i++)
        for(int j=0;j<25;j++)
            for(int k=0;k<_;k++)
                a[i][j][k]=inf;
    for(int i=1;i<=q[0];i++)
        scanf("%lld",&a[0][0][i]);
    for(int i=1;i<=q[0];i++){
        scanf("%lld",&q[i]);
        if(q[i]==1){
            d++;mp[d]=i;
            scanf("%lld%lld",&x[d],&y[d]);
        }
        else{
            int x;
            scanf("%lld",&x);
            if(x==1)f1^=1;
            if(x==2)f2^=1;
            if(x==3)f3^=1;
        }
        if(!f1)a[1][0][i]=a[0][0][i];
        if(!f2)a[2][0][i]=a[0][0][i];
        if(!f3)a[3][0][i]=a[0][0][i];
    }
    if(!d){
        printf("0\n");
        return 0;
    }
    lg[1]=0;
    for(int i=2;i<=q[0];i++)
        lg[i]=lg[i>>1]+1;
    mp[0]=0;y[0]=1;
    ST(1);ST(2);ST(3);
    for(int i=0;i<=d;i++)
        for(int j=0;j<=d;j++)
            for(int k=0;k<=d;k++)
                f[i][j][k]=inf;
    f[0][0][0]=0;d=0;
    for(int i=1;i<=q[0];i++){
        if(q[i]==2)continue;
        d++;
        int Cost1,Cost2,Cost3,cost1,cost2,cost3,c1ost,c2ost,c3ost;
        cost1=a[1][0][mp[d]]*abs(x[d]-y[d]);
        c1ost=Min(1,mp[d-1],mp[d])*abs(x[d]-y[d-1]);
        cost2=a[2][0][mp[d]]*abs(x[d]-y[d]);
        c2ost=Min(2,mp[d-1],mp[d])*abs(x[d]-y[d-1]);
        cost3=a[3][0][mp[d]]*abs(x[d]-y[d]);
        c3ost=Min(3,mp[d-1],mp[d])*abs(x[d]-y[d-1]);
        for(int j=0;j<d;j++)
            for(int k=0;k<d;k++){
                f[d][j][k]=min(f[d][j][k],f[d-1][j][k]+c1ost+cost1);
                f[j][d][k]=min(f[j][d][k],f[j][d-1][k]+c2ost+cost2);
                f[j][k][d]=min(f[j][k][d],f[j][k][d-1]+c3ost+cost3);
                if(j==d-1)continue;
                Cost1=Min(1,mp[k],mp[d])*abs(x[d]-y[k]);
                Cost2=Min(2,mp[k],mp[d])*abs(x[d]-y[k]);
                Cost3=Min(3,mp[k],mp[d])*abs(x[d]-y[k]);
                f[d][d-1][j]=min(f[d][d-1][j],f[k][d-1][j]+Cost1+cost1);
                f[d][j][d-1]=min(f[d][j][d-1],f[k][j][d-1]+Cost1+cost1);
                f[d-1][d][j]=min(f[d-1][d][j],f[d-1][k][j]+Cost2+cost2);
                f[j][d][d-1]=min(f[j][d][d-1],f[j][k][d-1]+Cost2+cost2);
                f[d-1][j][d]=min(f[d-1][j][d],f[d-1][j][k]+Cost3+cost3);
                f[j][d-1][d]=min(f[j][d-1][d],f[j][d-1][k]+Cost3+cost3);
            }
    }
    ans=inf;
    for(int j=0;j<d;j++)
        for(int k=0;k<d;k++){
            ans=min(ans,f[d][j][k]);
            ans=min(ans,f[j][d][k]);
            ans=min(ans,f[j][k][d]);
        }
    printf("%lld\n",ans);
    return 0;
}码风严谨

Postscribe

调了两年，怒了，不写注释了，让代码自己猜。

在新的一年里，祝大家心想事成，万事如意~~~