Luogu 3959 [NOIP2017] 宝藏

NOIP2017最后一道题

挺难想的状压dp。

受到深度的条件限制，所以一般的状态设计带有后效性，这时候考虑把深度作为一维，这样子可以保证所有状态不重复计算一遍。

神仙预处理：先处理出一个点连到一个集合所需要的最小代价，然后再处理出一个集合连到一个集合所需要的最小代价

设$g_{s, t}$表示从s集合连到t集合的最小代价， $f_{i, j}$表示当前深度为i，挖到集合s的最小代价，有转移：

　　　　$f_{i, s} = min(g_{s, t} * (i - 1) + f_{i - 1, t})$ t是s的子集

最后的答案　　$ans = min(f_{i, maxS})$ $(0<i<n)$

可以发现这样子最优答案一定会被计算到。

时间复杂度$O(3^{n} * 2 ^ {n} * n)$.

Code:

#include <cstdio>

#include <cstring>

using namespace std;

const int N = ;

const int S = ( << ) + ;

const int inf = 0x3f3f3f3f;

int n, m, e[N][N], h[N][S], g[S][S], f[N][S];

inline void read(int &X) {

    X = ;

    char ch = ;

    int op = ;

    for(; ch > '' || ch < ''; ch = getchar())

        if(ch == '-') op = -;

    for(; ch >= '' && ch <= ''; ch = getchar())

        X = (X << ) + (X << ) + ch - ;

    X *= op;

}

inline int min(int x, int y) {

    return x > y ? y : x;

}

inline void chkMin(int &x, int y) {

    if(y < x) x = y;

}

int main() {

    read(n), read(m);

    memset(e, 0x3f, sizeof(e));

    for(int x, y, v, i = ; i <= m; i++) {

        read(x), read(y), read(v);

        e[x][y] = min(e[x][y], v);

        e[y][x] = min(e[y][x], v);

    }

/*    for(int i = 1; i <= n; i++, printf("\n"))

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

            printf("%d ", e[i][j]);   */

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

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

            h[i][s] = inf;

            if(!(s & ( << (i - ))))

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

                    if(s & ( << (j - )))

                        chkMin(h[i][s], e[i][j]);

        }

    }

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

        for(int t = s & (s - ); t; t = s & (t - )) {

            int x = s ^ t;

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

                if(x & ( << (i - )))

                    g[s][t] = min(g[s][t] + h[i][t], inf);

        }

    }

    memset(f, 0x3f, sizeof(f));

    for(int i = ; i <= n; i++)    f[][ << (i - )] = ;

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

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

            for(int t = s & (s - ); t; t = s & (t - )) {

                int tmp;

                if(g[s][t] != inf) tmp = g[s][t] * (i - );

                else tmp = inf;

                if(f[i - ][t] != inf)

                    chkMin(f[i][s], f[i - ][t] + tmp);

            }

        }

    }

    int ans = inf;

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

        chkMin(ans, f[i][( << n) - ]);

    printf("%d\n", ans);

    return ;

}

巴特西

Luogu 3959 [NOIP2017] 宝藏

最新文章

热门文章