bzoj2516 电梯

传送门：http://www.lydsy.com/JudgeOnline/problem.php?id=2516

【题解】

状压dp。

$f_{sta,i}$表示状态为sta，当前在第i层的最小花费时间。状态是个三进制表示，0代表没进过电梯；1代表在电梯里；2表示进过电梯，出来了。

然后考虑当前状态转移出去即可。复杂度$O(Cas * 3^n * nm)$，成功垫底。

据说用2个二进制可以更快（逃

# include <vector>

# include <stdio.h>

# include <string.h>

# include <iostream>

# include <algorithm>

// # include <bits/stdc++.h>

using namespace std;

typedef long long ll;

typedef long double ld;

typedef unsigned long long ull;

const int M = 5e5 + ;

const int mod = 1e9+, inf = 1e9;

const int STATUS_SIZE =  + ;

int n, m, fir, bin[];

int f[STATUS_SIZE][], s[];

struct pa {

    int t, a, b;

    pa() {}

    pa(int t, int a, int b) : t(t), a(a), b(b) {}

}p[];

vector<int> ps;

# define abs(x) ((x) >  ? (x) : -(x))

# define bit(x, i) (((x) / bin[i]) % )

# define dist(i, j) (abs(ps[j-] - ps[i-]))

inline int getid(int x) {

    return lower_bound(ps.begin(), ps.end(), x) - ps.begin() + ;

}

inline void gmin(int &a, int b) {

    if(b < a) a = b;

}

inline void sol() {

    cin >> n >> fir;

    ps.clear(); ps.push_back(fir);

    for (int i=; i<=n; ++i) {

        scanf("%d%d%d", &p[i].t, &p[i].a, &p[i].b);

        ps.push_back(p[i].a);

        ps.push_back(p[i].b);

    }

    sort(ps.begin(), ps.end());

    ps.erase(unique(ps.begin(), ps.end()), ps.end());

    for (int i=; i<=n; ++i) {

        p[i].a = getid(p[i].a);

        p[i].b = getid(p[i].b);

    }

    fir = getid(fir); m = ps.size();

    for (int sta=; sta<bin[n]; ++sta) for (int i=; i<=m; ++i) f[sta][i] = inf;

    for (int i=; i<=m; ++i) f[][i] = dist(i, fir);

    for (int sta=; sta<bin[n]; ++sta) {

        for (int i=; i<=m; ++i) {

            for (int j=; j<=n; ++j) {

                if(bit(sta, j-) == ) gmin(f[sta+bin[j-]][p[j].b], max(f[sta][i] + dist(p[j].b, i), p[j].t));

                else if(bit(sta, j-) == ) gmin(f[sta+bin[j-]][p[j].a], max(f[sta][i] + dist(p[j].a, i), p[j].t));

            }

        }

    }

    int ans = inf;

    for (int i=; i<=m; ++i) gmin(ans, f[bin[n]-][i]);

    cout << ans << endl;

}

int main() {

    bin[] = ; for (int i=; i<=; ++i) bin[i] = bin[i-]*;

    int T; cin >> T;

    while(T--) sol();

    return ;

}