The solution of「P2704 [NOI2001] 炮兵阵地」

· · 题解

\textup{[NOI2001] 炮兵阵地}

\textup{Link.}

发现自己不会状压了，做点题。

\textup{\textup{Description}}

给定有山地的地图，放置攻击范围为一个大小为两格十字架的炮兵，不能放在山上，两方攻击范围可以重叠。

问最多能放置多少个互不攻击的炮兵。

\textup{\textup{Solution}}

注意到 N \le 100 不好处理，但是 M \le 10 可以状压。

又因为当前行的炮兵只会受到前两行的影响，于是有状态定义 f_{h,i,j} 表示前 h 行中，当前行状态为 i，上一行状态为 j。

这样我们要转移到下一行就十分方便了。

我们计算一下复杂度，发现空间似乎存不下，考虑优化。

因为每行内炮兵互不攻击的方案数是有限的，算出大致为 60，所以考虑只枚举行内合法状态。

这样既可以节省复杂度，还可以解决行内合法的问题。

于是定义 mask_i 表示第 i 中合法状态，转移时枚举即可。

实现上，我们将地图中山地也状压，通过位运算可以清晰地得出当前状态是否合法。

具体的，我们枚举出新的状态后，将原先行进行与运算，判断相邻行间列的合法性，再转移即可。

注意，要初始化第 0 行，方便第一行的转移。

时间复杂度：O(N \cdot cnt^3)，空间：O(N \cdot cnt^2), \ cnt \le 65。

\textup{Code}

const int MAXN = 105;
const int MAXM = 105;
int N, M;
int mp[MAXN];
int dp[MAXN][MAXM][MAXM];
int mask[MAXN], cnt;

bool chk( int x ){ return !( ( x & ( x << 1 ) ) || ( x & ( x << 2 ) ) ); }

void solve(){//预处理合法状态
    for( int i = 0; i < ( 1 << M ); i ++ )
        if( chk( i ) ) mask[++ cnt] = i;
}
int main(){
    cin >> N >> M;
    for( int i = 1; i <= N; i ++ ){
        for( int j = 0; j < M; j ++ ){
            char k;
            cin >> k;
            if( k == 'H' ) mp[i] |= ( 1 << j );
        }
    }
    memset( dp, -1, sizeof dp );
    solve();
    for( int i = 1; i <= cnt; i ++ ){//初始化
        if( !( mask[i] & mp[1] ) )
            dp[1][i][0] = __builtin_popcount( mask[i] );
    }
    for( int h = 2; h <= N; h ++ )
    for( int i = 1; i <= cnt; i ++ ){
        if( mask[i] & mp[h] ) continue;
        for( int j = 1; j <= cnt; j ++ ){
            if( ( mask[i] & mask[j] ) || mask[j] & mp[h - 1] ) continue;
            for( int k = 0; k <= cnt; k ++ ){
                if( k == 0 && h == 2 && dp[h - 1][j][0] != -1 ){
                    dp[h][i][j] = max( dp[h][i][j], dp[h - 1][j][0] + __builtin_popcount( mask[i] ) );
                }
                if( h >= 3 && ! ( mask[i] & mask[k] ) && !( mp[h - 2] & mask[k] ) && dp[h - 1][j][k] != -1 )
                    dp[h][i][j] = max( dp[h][i][j], dp[h - 1][j][k] + __builtin_popcount( mask[i] ) );
            }
        }
    }
    int ans = -0x3f3f3f3f;
    for( int i = 1; i <= cnt; i ++ ){
        for( int j = 0; j <= cnt; j ++ ){
            ans = max( ans, dp[N][i][j] );
        }
    }
    cout << ans;
    return 0;
}

\textup{Last}

审核管理员辛苦了，如果您有什么看不懂、我太弱了所以讲错了的地方，请您在评论区指出或找我，我会一定解答并且修改本题解。

如果您觉得本文写的还不错，那可以留个赞吗?

QWQ。

谢谢你看到这里~