1 条题解

  • 0
    @ 2025-10-8 16:48:54
    /*
    注意:
    f[i]      表示 楼层i  "能够有人在" 所花的时间,
    lift[i].t表示 电梯i  "能够有人在" 所花的时间,以后 楼层x 能够有人在(通过电梯i)只需要lift[i].t +等待电梯出现的时间 
    
    想通:
    1、想省时间,乘坐电梯只能往下。 
    2、电梯每下一层时间为0,最后再加n-1(减少状态方程的复杂性)
    3、电梯j 让 楼层i 有人是不需要等待电梯出现的时间的( "人出电梯" 不需要等待电梯出现的时间)
    4、楼层i 让 电梯j 有人是需要等待电梯出现的时间的,且再加上之前让 楼层i  "能够有人在" 的时间( "人进电梯" 需要等待电梯出现的时间)
    
    过程: 
    1、从上到下枚举每一层,在当前 楼层i 只有一件事情就是让第i层能够有人在的最少时间f[i]:
    第i层的地板对着所有听得到的电梯说:哪个电梯有人在啊?快来更新我的f[i] 
    2、然后用这个最小的f[i],更新让(其他)电梯j"能够有人在"所花的最少时间lift[j].t 
    
    */
    
    #include <bits/stdc++.h>
    using namespace std;
    struct node
    {
        int st,ed;
        double t;
        node(){t=999999999.0;}
    }lift[210];
    double ET(int a,int b)//计算等待电梯出现的时间 
    {
        return (a*(a+1)+b*(b+1))/2.0/(a+b+1);
    }
    double f[11100];
    int main()
    {
        int m,n;scanf("%d%d",&m,&n);
        for(int i=1;i<=m;i++)scanf("%d%d",&lift[i].st,&lift[i].ed);
        for(int i=0;i<n;i++)f[i]=999999999.0;f[n]=0;
        for(int i=n;i>=1;i--)
        {
            for(int j=1;j<=m;j++) //解决f[i](不再改),即让第i层 "能够有人在" 所花的时间 
            {
                if(lift[j].st<=i && i<=lift[j].ed)
                    f[i]=min(f[i], lift[j].t);
            }
              
            for(int j=1;j<=m;j++) //解决lift[j]的t,即让lift[j] "能够有人在" 所花的时间
            {
                if(lift[j].st<=i && i<=lift[j].ed)
                    lift[j].t=min(lift[j].t,f[i]+ET(i-lift[j].st,lift[j].ed-i));
            }
        }
        printf("%.5lf\n",f[1]+n-1);
        return 0;
    }
    
    • 1

    *【动态规划:状态设计DP】乘电梯

    信息

    ID
    248
    时间
    1000ms
    内存
    128MiB
    难度
    3
    标签
    递交数
    59
    已通过
    33
    上传者