洛谷 P2704 [NOI2001]炮兵阵地

题意简述

给定一张地图,有山地H,平原P,平原可放置炮兵,

炮兵可以攻击沿横向左右各两格,沿纵向上下各两格的区域

求最多放几个炮兵,使他们两两攻击不到

题解思路

枚举第i层,第i - 1层,第i - 2层的状态,滚动数组

dp[i & 1][j][k] = max(dp[(i + 1) & 1][k][l] + __builtin_popcount(j));

代码

#include <cstdio>
#include <iostream>
#include <algorithm>
using namespace std;
int n, m, M, ans;
int map[110];
int dp[3][1050][1050];
char ch;
void maxx(int &x, int y) {x = max(x, y); }
int main()
{
ios::sync_with_stdio(false);
cin >> n >> m;
for (register int i = 1; i <= n; ++i)
for (register int j = 1; j <= m; ++j)
{
cin >> ch;
if (ch == 'P') map[i] <<= 1;
else map[i] = map[i] << 1 | 1;
}
M = 1 << m;
for (register int i = 1; i <= n; ++i)
for (register int j = 0; j < M; ++j)
if (!(j & map[i]) && !(j & j << 1) && !(j & j << 2))
for (register int k = 0; k < M; ++k)
if (!(k & j) && !(k & k << 1) && !(k & k << 2))
for (register int l = 0; l < M; ++l)
if (!(j & l) && !(j & k) && !(l & l << 1) && !(l & l << 2))
maxx(dp[i & 1][j][k], dp[(i + 1) & 1][k][l] + __builtin_popcount(j));
for (register int i = 0; i < M; ++i)
for (register int j = 0; j < M; ++j)
maxx(ans, dp[n & 1][i][j]);
cout << ans << endl;
}
上一篇:python -- 计算数学题--用程序解决问题1


下一篇:linux根目录下文件夹概览