Let us define the following terms:

• A black connected component is a maximal segment consisting of black squares.
• A white connected component is a maximal segment consisting of white squares.
• A connected component of pieces is a maximum segment of squares with a piece on each of them.

Solution

The necessary and sufficient condition for a final placement of pieces to be valid

is (A) or (B), where:

(A)

We define the following:

• a1: the white square at the middle of three consecutive white squares;
• a2: a black connected component;
• a3: a black square.

The condition: there is a way to encircle all connected component of pieces by encircling them one by one, as follows:

1. You may choose one connected component of pieces containing a1 and encircle it, or not.
2. You may choose any number of connected components of pieces containing a2 and encircle them.
3. You may choose one connected component of pieces containing a3 and encircle it, or not.

(B)

Similar to (A), but white and black are inverted.

DP

Let us consider placements of pieces that satisfy (A) and also put a stone on every square where it is required. By maintaining only the states where those conditions are met, we can find the minimum number of stones we need to put. More specifically, we make the DP table have the indices below and maintain the minimum number of stones placed while satisfying the conditions.

• The number of squares already considered
• The flag of whether rule 1 is already used
• The flag of whether rule 3 is already used
• The flag of whether Square \(i\) gets a piece
  • (When Square \(i\) gets a piece) the flag of whether the current connected component of pieces contains a1
  • (When Square \(i\) gets a piece) the flag of whether the current connected component of pieces contains the left end of a2
  • (When Square \(i\) gets a piece) the flag of whether the current connected component of pieces contains a2
  • (When Square \(i\) gets a piece) the flag of whether the current connected component of pieces contains a3

We will do a similar DP for condition (B), and the answer is the smaller of the results.

The validity of the solution

Sufficiency

We can realize a final placement of pieces satisfying the condition, as follows:

1. Put a piece on a1.
2. Put a piece on each a2.
3. Put a piece on a3.
4. Expand each connected component of pieces in some order.

Necessity

First, we can see that we do not have to decrease the number of connected components of pieces. That is, we do not have to put a piece on Square \(i\) when there is a connected component of Squares \(l\) through \(i-1\) and another of Squares \(i+1\) through \(r\). This is because, after making the connected component of Squares \(l\) through \(i-1\), we can put pieces on Squares \(i, i+1, \dots, r\) in this order to get the same result.

After putting at least one piece for each connected component of pieces in the final placement, we can easily expand each connected component, so we will only consider the first phase of making new connected components.

During the process of putting pieces one by one, let us focus on which of the following patterns each connected component falls into:

• a: Adjacent to only white squares.
• b: Adjacent to only black squares.
• c: Adjacent to both colors of squares.

To make a new connected component, one of the following must hold: all of the existing connected components are “a,” or all of them are “b.”

We can prove that it is unnecessary to use “a” sometimes and use “b” the other times. That is, if we first choose a or b and stick to that choice when making a new connected component, we can still achieve the optimal placement.

Let us show this. Assume that, at some point, all connected components were “a,” but now they are all “b.” We are done if we can show that we can achieve the same placement of pieces not via the state where all of them are “a.” For each connected component, there are only two cases:

• A connected component of pieces that was “a1” at the point
  • If we add pieces to such a connected component of pieces so that it is adjacent to only black squares, we must put pieces on the whole white connected component containing a1.
• A connected component of pieces that was placed on a black connected component
  • If we add pieces to such a connected component of pieces so that it is adjacent to only black squares, we must put pieces on both the white connected component to the immediate left and the white connected component to the immediate right. We can instead put pieces on just one of those components.

Then, we can see that we have no choice but (A) or (B).

Sample Implementation in C++