Grid-Based State Compression DP: A Deep Dive into No-Retreat Properties and Bitwise Operations

Core Logic and Mathematical Principles

The essence of Grid-based State Compression Dynamic Programming is to utilize spatial locality dependencies to reduce the high-dimensional constraints of a two-dimensional grid topology into a one-dimensional state vector interwoven between states.

In Section 17.1, we explored point set compression using the "vertex set" as the compression scale. However, when dealing with grid problems (such as king placement and non-attacking problems), the constraints typically only exist between adjacent rows and columns.

1. Physical Isolation of No-Retreat Property

Assuming a grid of size $N \times M$, when placing pieces, if we advance in a topological order of "top-down, row by row decision-making," then when placing pieces on the $i^{th}$ row:

The legality of this row depends solely on the horizontal conflicts within the row.
Whether this row conflicts with historical placements depends only on its conflicts with the $(i-1)^{th}$ row in terms of vertical and diagonal conflicts.
As for the configurations of the $(i-2)^{th}$ row and above, they are physically isolated from the $i^{th}$ row by the $(i-1)^{th}$ row and have no direct influence on it.

Therefore, we do not need to record the overall appearance of the chessboard; we only need to compress the placement configuration of the "current row" into a binary mask $S$, which perfectly satisfies the no-retreat property.

2. Bitwise Operation Conflict Check Matrix

Assuming a grid with $M$ columns in a row, we use the binary state $S$ to represent the placement of pieces in that row (1 means occupied, 0 means empty).

Adaptive Row Check: If two pieces cannot be adjacent in the same direction (as in the king and non-attacking model):
Horizontal Conflict: If (S & (S << 1)) is not 0, it indicates that there are horizontally adjacent pieces, and this state is invalid.
Cross-row State Machine Transition Check: Let the current state of the $i^{th}$ row be $S$ and the previous state of the $(i-1)^{th}$ row be $S_{pre}$:
Vertical Conflict: If (S & S_pre) is not 0, it indicates that there are vertically adjacent pieces.
Left Diagonal Conflict: If (S & (S_pre << 1)) is not 0, it indicates that a piece from the previous row is directly adjacent to the left below the current row piece.
Right Diagonal Conflict: If (S & (S_pre >> 1)) is not 0, it indicates that a piece from the previous row is directly adjacent to the right below the current row piece.

State Design and Algorithm Derivation

Taking the classic "Non-Attacking (King)" problem as an example: In an $N \times N$ chessboard, place $K$ kings such that they do not attack each other. The task is to find the total number of valid configurations to place $K$ kings.

1. State Space Definition

Let the state $f[i][j][S]$ represent the number of valid configurations when the first $i$ rows have been decided, with $j$ kings already placed on the board, and the current placement mask of kings in the $i^{th}$ row is $S$.

2. State Transition Equation

For the current row state $S$, we must first ensure its legality within the row. Next, we need to obtain the number of kings contributed by the current row using the operator __builtin_popcount(S), denoted as $c$.

$$\forall S_{pre} \text{ compatible with } S, \quad f[i][j][S] = \sum f[i-1][j - c][S_{pre}]$$

Where "$S_{pre} \text{ compatible with } S$" must strictly pass the three cross-row bitwise checks described above.

C++ Standard Source Code (NOIP Style)

The following code is an industrial-grade standard implementation for the "Non-Attacking/King Placement" problem. The code includes legal state space preprocessing optimizations to significantly reduce constants, ensuring a runtime of 0.00s under Linux g++ -O2.

#include <iostream>
#include <vector>
#include <cstring>

using namespace std;

const int MAXN = 10;
const int MAXK = 100;

long long f[MAXN][MAXK][1 << MAXN];
vector<int> valid_states; // Preprocess to store all valid row states to avoid invalid enumeration
int state_weights[1 << MAXN]; // Preprocess the count of 1's in each binary state (i.e., number of kings)

int n, k_total;

// Preprocessing function: Eliminate states with horizontal conflicts and calculate weights
void preprocess() {
    int max_state = 1 << n;
    for (int s = 0; s < max_state; ++s) {
        // No adjacent kings horizontally
        if (!(s & (s << 1))) {
            valid_states.push_back(s);
            state_weights[s] = __builtin_popcount(s); // Quickly calculate the number of 1's in binary
        }
    }
}

int main() {
    ios_base::sync_with_stdio(false);
    cin.tie(NULL);

    if (!(cin >> n >> k_total)) return 0;

    preprocess();

    // Boundary initialization: 0 pieces in the 0th row, 0 kings, mask 0 has 1 configuration
    f[0][0][0] = 1;

    // Topological axis: advance row by row
    for (int i = 1; i <= n; ++i) {
        // Enumerate current row state S (must be from preprocessed valid states)
        for (int s : valid_states) {
            int c = state_weights[s]; // Number of kings placed in the current row

            // Enumerate previous row state S_pre (also from valid set)
            for (int s_pre : valid_states) {
                // Comprehensive check for cross-row conflicts: vertical, left diagonal, right diagonal
                if (s & s_pre) continue;
                if (s & (s_pre << 1)) continue;
                if (s & (s_pre >> 1)) continue;

                // Enumerate total number of kings placed up to the previous row j
                for (int j = c; j <= k_total; ++j) {
                    f[i][j][s] += f[i - 1][j - c][s_pre];
                }
            }
        }
    }

    // Global result collection: horizontally accumulate the number of configurations for all possible states in the last row
    long long ans = 0;
    for (int s : valid_states) {
        ans += f[n][k_total][s];
    }

    cout << ans << "\n";

    return 0;
}

NOIP Practical Pitfall Guide

1. Blindly Using Brute Force Enumeration Causes Implicit Explosion in Time Complexity

Phenomenon: In grid compression, directly using ordinary loops for (int s = 0; s < (1<<n); ++s) and for (int s_pre = 0; s_pre < (1<<n); ++s_pre). If $N=10$, the number of states per row reaches $1024$. The computational load of two layers of state loops is $1024 \times 1024 \approx 10^6$, multiplied by the number of rows and kings, leading to a direct explosion in constants causing Time Limit Exceeded.
Avoidance Method: Must perform valid state preprocessing. For example, when $N=10$, the actual number of valid states with non-adjacent kings in a row is only 144. Extracting these 144 states into std::vector and then running the inner loop reduces the single-layer loop count from $1024$ to $144$, compressing the overall constant by nearly 50 times.

2. Bit Shift Boundary Overflow Risks

Phenomenon: When checking diagonal conflicts, directly writing s & (s_pre << 1). When $N$ approaches the integer boundary (or in more macro grid compressions), if the shift operation is not properly bounded, high bits may pollute preceding memory, or undefined behavior may occur due to sign bits.
Avoidance Method: When performing bit shift checks, if concerned about high bit pollution, actively truncate by bitwise ANDing with the full set: (s_pre << 1) & ((1 << n) - 1).

Classic NOIP/Luogu Problems

1. Luogu P1896 [SCOI2005] Non-Attacking

Problem Description: This is the textbook-level classic model described above.
Problem Essence and Solution Idea: A grid-based DP with independent counting dimensions. By introducing a third dimension $j$, the total number of kings is accurately constrained. Given the small data range ($N \le 9$), a single round of state set preprocessing and three nested loops can reliably pass.

2. Luogu P2704 [NOI2001] Artillery Position

Problem Description: Deploy artillery on an $N \times M$ grid with terrain restrictions. The artillery's attack range is 2 squares in the up, down, left, and right directions. This means that any two artillery pieces in the same row must be at least 2 squares apart, and there are mutual conflicts between artillery pieces in adjacent rows and even those separated by a row. The task is to find the maximum number of artillery pieces that can be deployed. $N \le 100, M \le 10$.
Problem Essence and Solution Idea: Cross-Multi-Level Dependency Grid-Based High-Dimensional Compression DP.
Core Difficulty: The artillery's vertical attack range reaches 2 squares, meaning that the decision for the $i^{th}$ row is constrained not only by the $(i-1)^{th}$ row but also strongly influenced by the $(i-2)^{th}$ row. Traditional two-dimensional state grids cannot support the lineage tracing of two generations.
State Design: The state must be expanded. Let $f[i][S][S_{pre}]$ represent the maximum number of artillery pieces that can be deployed when the first $i$ rows have been decided, with the current state of the $i^{th}$ row being $S$ and the previous state of the $(i-1)^{th}$ row being $S_{pre}$.
State Transition:

$$f[i][S][S_{pre}] = \max \{ f[i-1][S_{pre Visited}][S_{pre\_pre}] \} + \text{count}(S)$$

When checking, in addition to performing the row-internal spacing check (S & (S << 1)) == 0 && (S & (S << 2)) == 0, it must also satisfy (S & S_pre) == 0 and (S & S_pre_pre) == 0. By adding an extra state dimension, it successfully decouples the second-order spatial no-retreat property, making it a must-solve problem for advanced grid compression.