题解 CF983C 【Elevator】

DPair · 2020-08-12 12:04:15 · 题解

【前言】

这个做法十分暴力，复杂度似乎也不对，但还是过了。。。（几乎每个点都卡着时限），仅供参考，肯定有更优秀的解法。（最后跑了 1.49min 你敢信？）

【思路】

首先我们发现这是一个最优化问题，考虑 DP 。

这个做法的状态设计十分暴力，不难发现某一状态下电梯的状态只与电梯中每个人的目的地与电梯所在楼层有关，而与电梯中人的编号是无关的。

这不难证明，如果按人的编号进行 n 次DP，并保证当前编号的人上了电梯（不一定要下电梯），那么每次DP时都不会出现编号大的先上了电梯的不合法情况。

由于电梯只有 4 个位置，考虑设置一个五维数组。（ n 那一维直接滚动数组滚掉了，这里不赘述）

设：

表示有一批人，他们分别要到达 k1, k2, k3, k4 楼层且电梯在 j 层，这个状态表示送走这批人时达到这个状态，所需要的最小时间。

但由于电梯不仅要送人，还要接人，因此再设一个五维数组。

设：

表示有一批人，他们分别要到达 k1, k2, k3, k4 楼层且电梯在 j 层，这个状态表示接走这批人时达到这个状态所需要的最小时间。

以上当 k=0 时，表示这个位置为空，可以接人。

下面考虑状态转移。

首先是送人环节：

这是显然的，表示你的电梯从 j 层走到了 k1,k2,k3,k4 ，去送人，而且你送人还需要 1 ，单位的时间，然后这个位置就没人了。

由于要送 4 个人，考虑循环 4 次。

然后是接人（实际实现中先接人再送人）：

也很显然，你只有有空位才能接一个人。

然后接完人之后电梯的状态其实就是你送人的状态。

然后代码就很好实现了。

最后，由于电梯可以停在任意一个位置，答案就是：

最终复杂度 O(n*10^5) ，还有大量常数，但就是过了。

代码很好实现：

【代码】

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
typedef unsigned long long ULL;
typedef long double LD;
typedef unsigned int UI;
typedef pair <int, int> pi;

template <typename T>
inline T mn(T x, T y) {return x < y ? x : y;}
template <typename T>
inline T mx(T x, T y) {return x > y ? x : y;}
template <typename T>
inline void chmin(T &x, T y) {(x > y) && (x = y);}
template <typename T>
inline void chmax(T &x, T y) {(x < y) && (x = y);}

template <typename T>
inline void read(T &x){
    x = 0;int fu = 1;
    char c = getchar();
    while(c > 57 || c < 48){
        if(c == 45) fu = -1;
        c = getchar();
    }
    while(c <= 57 && c >= 48){
        x = (x << 3) + (x << 1) + c - 48;
        c = getchar();
    }
    x *= fu;
}
template <typename T>
inline void fprint(T x){
    if(x < 0) putchar(45), x = -x;
    if(x > 9) fprint(x / 10);
    putchar(x % 10 + 48);
}
template <typename T>
inline void fprint(T x, char ch){
    fprint(x);putchar(ch);
}
//下面是有效代码
int dp[10][10][10][10][10], g[10][10][10][10][10];
int a[2010], b[2010], n;
int main(){
    read(n);
    memset(dp, 31, sizeof(dp));dp[1][0][0][0][0] = 0;//初始化，电梯在一楼，空的
    for (register int i = 1;i <= n;i ++){
        read(a[i]);read(b[i]);
        memset(g, 31, sizeof(g));
        for (register int j = 1;j <= 9;j ++){//接人
            for (register int k1 = 0;k1 <= 9;k1 ++){
                for (register int k2 = 0;k2 <= 9;k2 ++){
                    for (register int k3 = 0;k3 <= 9;k3 ++){
                        for (register int k4 = 0;k4 <= 9;k4 ++){
                            if(!k1) chmin(g[a[i]][b[i]][k2][k3][k4], dp[j][k1][k2][k3][k4] + abs(j - a[i]) + 1);
                            if(!k2) chmin(g[a[i]][k1][b[i]][k3][k4], dp[j][k1][k2][k3][k4] + abs(j - a[i]) + 1);
                            if(!k3) chmin(g[a[i]][k1][k2][b[i]][k4], dp[j][k1][k2][k3][k4] + abs(j - a[i]) + 1);
                            if(!k4) chmin(g[a[i]][k1][k2][k3][b[i]], dp[j][k1][k2][k3][k4] + abs(j - a[i]) + 1);
                        }
                    }
                }
            }
        }
        memcpy(dp, g, sizeof(dp));
        for (register int k = 1;k <= 4;k ++){//送人×4
            for (register int j = 1;j <= 9;j ++){
                for (register int k1 = 0;k1 <= 9;k1 ++){
                    for (register int k2 = 0;k2 <= 9;k2 ++){
                        for (register int k3 = 0;k3 <= 9;k3 ++){
                            for (register int k4 = 0;k4 <= 9;k4 ++){
                                if(k1) chmin(dp[k1][0][k2][k3][k4], dp[j][k1][k2][k3][k4] + abs(j - k1) + 1);
                                if(k2) chmin(dp[k2][k1][0][k3][k4], dp[j][k1][k2][k3][k4] + abs(j - k2) + 1);
                                if(k3) chmin(dp[k3][k1][k2][0][k4], dp[j][k1][k2][k3][k4] + abs(j - k3) + 1);
                                if(k4) chmin(dp[k4][k1][k2][k3][0], dp[j][k1][k2][k3][k4] + abs(j - k4) + 1);
                            }
                        }
                    }
                }
            }
        }
    }
    int ans = 0x3f3f3f3f;
    for (register int i = 1;i <= 9;i ++) chmin(ans, dp[i][0][0][0][0]);
    fprint(ans, 10);
    return 0;
}