\(\mathcal{Description}\)

Link.（HDU 裂开了先放个私链 awa。）

在一个 \(n\times n\) 的方格图中，格子 \((i,j)\) 有权值 \(w_{i,j}\)，现可将一些不相邻的格子染黑，并保证白格子在四联通意义下存在哈密顿回路，方案的价值为染色格子权值之和。求方案的最大价值。

\(n\le10\)，数据组数 \(T\le30\)。

\(\mathcal{Solution}\)

Emmm...插头 DP 写得太少了，这题还算比较常规，所以只算记录一个板子叭。

令 \(f(i,j,S)\) 表示正要考虑 \((i,j)\) 时，轮廓线为 \(S\) 的最大价值。轮廓上的每条边有四种状态：无插头、左插头、右插头、黑格子，大力转移即可，注意用 hash 保存状态。

复杂度上界是 \(\mathcal O(n^34^{n+1})\)，但显然跑不满√

\(\mathcal{Code}\)

/*~Rainybunny~*/

#include <cstdio>

#include <cassert>

#include <cstring>

#define rep( i, l, r ) for ( int i = l, rep##i = r; i <= rep##i; ++i )

#define per( i, r, l ) for ( int i = r, per##i = l; i >= per##i; --i )

inline void chkmax( int& a, const int b ) { a < b && ( a = b ); }

const int MAXN = 10;

int n, w[MAXN + 5][MAXN + 5];

struct HashTable {

    static const int M = 299987;

    int node, head[M + 5], nxt[M + 5], key[M + 5], val[M + 5];

    inline void clear() {

        rep ( i, 1, node ) head[key[i] % M] = 0;

        node = 0;

    }

    inline void operator () ( const int s, const int v ) {

        int h = s % M, las = 0;

        for ( int i = head[h]; i; i = nxt[las = i] ) {

            if ( key[i] == s ) {

                return chkmax( val[i], v );

            }

        }

        if ( !las ) head[h] = ++node;

        else nxt[las] = ++node;

        key[node] = s, val[node] = v, nxt[node] = 0;

    }

} S[2];

inline int match( const int s, const int k ) {

    int v = s >> k >> k & 3;

    if ( v != 1 && v != 2 ) return -1;

    if ( v == 1 ) {

        int cnt = 1;

        rep ( i, k + 1, n ) {

            if ( int t = s >> i >> i & 3; t == 1 ) ++cnt;

            else if ( t == 2 && !--cnt ) return i;

        }

    } else {

        int cnt = 1;

        per ( i, k - 1, 0 ) {

            if ( int t = s >> i >> i & 3; t == 2 ) ++cnt;

            else if ( t == 1 && !--cnt ) return i;

        }

    }

    return assert( false ), -1;

}

inline bool check( const int s ) {

    rep ( i, 0, n ) {

        if ( ( s >> i >> i & 3 ) && ( s >> i >> i & 3 ) != 3 ) {

            return false;

        }

    }

    return true;

}

inline int solve() {

    S[0].clear(), S[0]( 0, 0 );

    int ret = 0;

    for ( int i = 1, sta = 0; i <= n; ++i ) {

        rep ( j, 1, S[sta].node ) {

            int d = S[sta].key[j] >> n >> n;

            assert( !d || d == 3 );

            ( S[sta].key[j] ^= d << n << n ) <<= 2;

        }

        for ( int j = 1; j <= n; ++j, sta ^= 1 ) {

            S[!sta].clear();

            rep ( k, 1, S[sta].node ) {

                int s = S[sta].key[k], v = S[sta].val[k];

                int pl = s << 2 >> j >> j & 3, pu = s >> j >> j & 3;

                int ql = match( s, j - 1 ), qu = match( s, j );

                s ^= ( pl << j << j >> 2 ) ^ ( pu << j << j );

                if ( !pl && !pu ) { // b

                    S[!sta]( s | 15 << j << j >> 2, v + w[i][j] );

                    if ( i == n && j == n ) chkmax( ret, v + w[i][j] );

                }

                if ( i < n && j < n

                  && ( !pl || pl == 3 ) && ( !pu || pu == 3 ) ) { // rd

                    S[!sta]( s | 9 << j << j >> 2, v );

                }

                if ( pl == 1 && pu == 2 && check( s ) ) { // lu, upd

                    if ( i == n && j == n ) chkmax( ret, v );

                    else if ( i == n && j == n - 1 && !( s >> n >> n & 3 ) ) {

                        chkmax( ret, v + w[n][n] );

                    }

                }

                if ( i < n && ( !pl || pl == 3 )

                  && ( pu == 1 || pu == 2 ) ) { // u-d

                    S[!sta]( s | pu << j << j >> 2, v );

                }

                if ( j < n && ( pl == 1 || pl == 2 )

                  && ( !pu || pu == 3 ) ) { // l-r

                    S[!sta]( s | pl << j << j, v );

                }

                if ( j < n && ( !pl || pl == 3 )

                  && ( pu == 1 || pu == 2 ) ) { // u-r

                    S[!sta]( s | pu << j << j, v );

                }

                if ( i < n && ( pl == 1 || pl == 2 )

                  && ( !pu || pu == 3 ) ) { // l-d

                    S[!sta]( s | pl << j << j >> 2, v );

                }

                if ( ~ql && ql != j && ~qu && qu != j - 1 ) { // lu

                    if ( pl == pu && pl == 1 ) {

                        S[!sta]( s ^ 3 << qu << qu, v );

                    } else if ( pl == pu && pl == 2 ) {

                        S[!sta]( s ^ 3 << ql << ql, v );

                    } else {

                        S[!sta]( s, v );

                    }

                }

            }

        }

    }

    return ret;

}

int main() {

    int T;

    for ( scanf( "%d", &T ); T--; ) {

        scanf( "%d", &n );

        rep ( i, 1, n ) rep ( j, 1, n ) scanf( "%d", &w[i][j] );

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

    }

    return 0;

}

巴特西

Solution -「HDU 6875」Yajilin

\(\mathcal{Description}\)

\(\mathcal{Solution}\)

\(\mathcal{Code}\)

最新文章

热门文章