histcat

Problem#

[NOI2001] Artillery Position#

The generals of the command intend to deploy their artillery troops on an $N\times M$ grid map.

A $N\times M$ map consists of $N$ rows and $M$ columns, where each cell may be mountainous terrain (represented by $\texttt{H}$) or plain terrain (represented by $\texttt{P}$), as shown in the figure below.

At most one artillery troop can be deployed on each cell of plain terrain (artillery troops cannot be deployed on mountainous terrain); the attack range of an artillery troop on the map is indicated by the black area in the figure:

If an artillery troop is deployed on the plain indicated by the gray area on the map, the black grids in the figure represent the area it can attack: two grids to the left and right horizontally, and two grids up and down vertically.

The other white grids on the map cannot be attacked. As can be seen from the figure, the attack range of the artillery is not affected by the terrain.

Now, the generals are planning how to deploy the artillery troops, ensuring that there is no friendly fire (i.e., ensuring that no two artillery troops can attack each other, meaning that no artillery troop is within the attack range of another), and determining the maximum number of our artillery troops that can be placed across the entire map area.

For $100%$ of the data, $N\le 100$, $M\le 10$, and it is guaranteed that the characters only include P and H.

Solution#

First, considering the data range, we can directly use state compression DP.

Consider designing the state.

Let’s try f[i][j] to represent the maximum number of artillery troops that can be placed when reaching row $i$, with the state of row $i$ represented in binary as $j$.

Let’s try to transition.

$f[i][j]$ needs to transition from $f[i-1][\sim]$, but the set of states in $f[i-1][\sim]$ cannot all be used, so the transition is not possible.

Consider adding a state.

f[i][j][fl] represents the maximum number of artillery troops that can be placed when reaching row $i$, with the state of row $i$ represented in binary as $j$ and the state of row $i-1$ represented as $fl$.

Now the transition is possible.

Implementation#

To check if it can be placed, perform a bitwise AND operation with the map and the binary representation, and also check the binary itself with its left-shifted versions by one and two bits.

The rest follows similarly.

Issues Encountered#

1. It is best for state compression DP to start indexing from 0.

2. Learned about rolling arrays.

Code#

#include<bits/stdc++.h>

using namespace std;

int read()
{
	int f = 1, x = 0;
	char ch = getchar();
	while(ch < '0' || ch > '9')
	{
		if(ch == '-') f = -1;
		ch = getchar();
	}

	while(ch >= '0' && ch <= '9')
	{
		x = x * 10 + ch - '0';
		ch = getchar();
	}
	return f * x;
}

int n, m;

int Map[110];// If it is 1, it represents mountainous terrain, 0 represents plain terrain 

int f[3][1 << 10][1 << 10]; // i, current state, previous row state 
int num_of_1[1 << 10];

int getsum(int x)
{
	int ans = 0;
	while(x)
	{
		x &= (x - 1);
		ans++;
	}
	return ans;
}

int main()
{

	for(int i = 0;i < (1 << 10);i++)
	{
		num_of_1[i] = getsum(i);
	}

	n = read(), m = read();
	char ch;
	for(int i = 0;i < n;i++)
	{
		for(int j = 0;j < m;j++)
		{
			cin >> ch;
			if(ch == 'H')
			{
				Map[i] |= (1 << j);
			}
		}
	}

	for(int j = 0;j < (1 << m);j++)
	{
		if(j & (j << 1) || j & (j << 2) || j & Map[0]) continue;
		f[0][j][0] = num_of_1[j];
	}

	for(int j = 0;j < (1 << m);j++)
	{
		for(int fl = 0;fl < (1 << m);fl++)
		{
			if(j & (j << 1) || j & (j << 2) || j & Map[1] || fl & (fl << 1) || fl & (fl << 2) || fl & Map[0] || j & fl || j & Map[1])
				continue;
			f[1][j][fl] = num_of_1[j] + num_of_1[fl];
		}
	}

	for(int i = 2;i < n;i++)
	{
		for(int j = 0;j <= (1 << m) - 1;j++)// Current row 
		{
			if(j & Map[i] || j & (j << 1) || j & (j << 2))
			{
				continue;
			}
		
			for(int fl = 0; fl <= (1 << m) - 1;fl++)// Previous row 
			{
				if(fl & Map[i - 1] || fl & (fl << 1) || fl & (fl << 2) || j & fl)
				{
					continue;
				}
			
				for(int fll = 0; fll < (1 << m);fll++)
				{
					if(fll & Map[i - 2] || fll & (fll << 1) || fll & (fll << 2) || j & fll || fl & fll)
					{
						continue;
					}
				
					f[i % 3][j][fl] = max(f[i % 3][j][fl], f[(i - 1) % 3][fl][fll] + num_of_1[j]);
				
				}
			}
		}
	}


	int ans = 0;

	for(int j = 0;j < (1 << m);j++)
	{
		for(int fl = 0;fl < (1 << m);fl++)
		{
			ans = max(ans, f[(n - 1) % 3][j][fl]);
		}
	}

	cout << ans << endl;
	return 0;
}