状压dp
[SCOI2005] 互不侵犯
题目描述
在N×N的棋盘里面放K个国王，使他们互不攻击，共有多少种摆放方案。国王能攻击到它上下左右，以及左上左下右上右下八个方向上附近的各一个格子，共8个格子。
注：数据有加强（2018/4/25）
输入格式
只有一行，包含两个数N，K （ 1 <=N <=9, 0 <= K <= N * N）
输出格式
所得的方案数
样例 #1
样例输入 #1
3 2
样例输出 #1
16
状压dp模板题
#include <bits/stdc++.h>
using namespace std;
#define ll long long
ll f[10][100][1 << 10]; //前i行放j个国王，当前行防止状态为k的方法数
int num[1 << 10];
int calc(int x)
{
int cnt = 0;
while (x)
{
if (x & 1)
cnt++;
x >>= 1;
}
return cnt;
}
int main()
{
int n, k;
cin >> n >> k;
for (int i = 0; i < (1 << n); i++)
{
num[i] = calc(i);
//cout << i << ' ' << num[i] << endl;
}
f[0][0][0] = 1;
ll ans = 0;
for (int i = 1; i <= n; i++)
{
for (int j = 0; j <= k; j++)
{
for (int st = 0; st < (1 << n); st++)
{
if (st & (st << 1))
continue;
for (int cur = 0; cur < (1 << n); cur++)
{
if (cur & (cur << 1))
continue;
if (st & cur)
continue;
if (st & (cur << 1))
continue;
if (st & (cur >> 1))
continue;
if (num[cur] > j)
continue;
f[i][j][cur] += f[i - 1][j - num[cur]][st];
}
}
}
}
for (int i = 0; i < (1 << n); i++)
{
ans += f[n][k][i];
}
cout << ans;
return 0;
}
[NOI2001] 炮兵阵地
题目描述
司令部的将军们打算在 \(N\times M\) 的网格地图上部署他们的炮兵部队。
一个 \(N\times M\) 的地图由 \(N\) 行 \(M\) 列组成，地图的每一格可能是山地（用 \(\texttt{H}\) 表示），也可能是平原（用 \(\texttt{P}\) 表示），如下图。
在每一格平原地形上最多可以布置一支炮兵部队（山地上不能够部署炮兵部队）；一支炮兵部队在地图上的攻击范围如图中黑色区域所示：
如果在地图中的灰色所标识的平原上部署一支炮兵部队，则图中的黑色的网格表示它能够攻击到的区域：沿横向左右各两格，沿纵向上下各两格。
图上其它白色网格均攻击不到。从图上可见炮兵的攻击范围不受地形的影响。
现在，将军们规划如何部署炮兵部队，在防止误伤的前提下（保证任何两支炮兵部队之间不能互相攻击，即任何一支炮兵部队都不在其他支炮兵部队的攻击范围内），在整个地图区域内最多能够摆放多少我军的炮兵部队。
输入格式
第一行包含两个由空格分割开的正整数，分别表示 \(N\) 和 \(M\)。
接下来的 \(N\) 行，每一行含有连续的 \(M\) 个字符，按顺序表示地图中每一行的数据。
输出格式
一行一个整数，表示最多能摆放的炮兵部队的数量。
样例 #1
样例输入 #1
5 4
PHPP
PPHH
PPPP
PHPP
PHHP
样例输出 #1
6
提示
对于 \(100\%\) 的数据，\(N\le 100\)，\(M\le 10\)，保证字符仅包含 P 与 H。
思路：
状压dp模板进阶版，这里的难点就是平地和山地了。
状态：\(f[i][j][k]\) 表示第 \(i\) 行放 \(j\) ，第 \(i-1\) 行放 \(k\)
方程：\(f[i][j][k]=max(f[i][j][k],f[i-1][k][p]+num[j])\)
我们可以把地形也用 \(01\)串存起来，如果是山地就 \(1\)，平原就 \(0\)，这样跟 \(st\) 作 \(and\) 运算的时候如果结果为0就说明可行
如：\(st\)：\(101010\)
\(mp[i]\)：\(010101\) 可行
\(mp[i]\)：\(100101\) 不可行，在山地上放炮兵了
还有就是一定要把状态预处理出来，不然内存存不下，\(100*(1<<10)*(1<<10)=104,857,600\)
#include<bits/stdc++.h>
using namespace std;
int mp[110];
int f[110][70][70];
vector<int> st;
vector<int> num;
int calc(int x)
{
int cnt = 0;
while(x)
{
if(x&1)
cnt++;
x >>= 1;
}
return cnt;
}
int main()
{
int n, m;
cin >> n >> m;
for (int i = 1; i <= n;i++)
{
for (int j = m; j >= 1;j--)
{
char c;
cin >> c;
if(c=='H')
mp[i] |= (1 << j - 1);
}
}
for (int i = 0; i < (1 << m);i++)
{
if(i&(i<<1))
continue;
if(i&(i<<2))
continue;
st.push_back(i);
num.push_back(calc(i));
}
int ans = 0;
for (int i = 1; i <= n;i++)
{
for (int j = 0;j<st.size();j++)
{
int cur = st[j];
if(cur&mp[i])
continue;
for (int k = 0; k < st.size();k++)
{
int last = st[k];
if(cur&last)
continue;
for (int p = 0; p < st.size();p++)
{
int pre = st[p];
if(cur&pre)
continue;
if(last&pre)
continue;
f[i][j][k] = max(f[i][j][k], f[i - 1][k][p] + num[j]);
ans = max(ans, f[i][j][k]);
}
}
}
}
cout << ans;
}