P2704 [NOI2001] 炮兵阵地 - 洛谷
题目大意（自己总结
给你一个01矩阵，1可以放炮兵，0不能放炮兵，每个炮兵放置之后上下左右四个方向两格不能再放置炮兵，求如何部署炮兵，让最后得到的炮兵数最多
题目主要实现思路
利用状压的性质，求出每行炮兵可能放置的位置（左右两格不能放置格外炮兵），因此可以减少枚举次数，设置dp-i-sa-sb,前i列，这一列状态为sa，前一列状态为sb可得转移方程dp-i-sa-sb = dp-i-sa-sb,dp-i-1_sb_sc+ct(sa这一行满足的炮兵数)，注意第一行要初始化
#include <bits/stdc++.h>#define int long longusing namespace std;const int N = 1e6 + 10;const int mod = 1e9 + 7;int g[110][20], sta[N];int k = 0;int n, m;int dp[110][1 << 10][1 << 10]; // 第i个当前为a状态下，前一个为b状态下void pre(int i, int s){ if (i >= m) { sta[k++] = s; return; } pre(i + 1, s); // 不选这一位 pre(i + 3, s | (1 << i)); // 选择这一位}int cont(int i, int s){ int ans = 0; for (int j = 0; j < m; j++) { if ((s >> j) & 1 && g[i][j]) { ans++; } } return ans;}void solve(){ cin >> n >> m; for (int i = 0; i < n; i++) { for (int j = 0; j < m; j++) { char c; cin >> c; g[i][j] = c == 'P' ? 1 : 0; } } // 预处理出每一行满足条件的结果 pre(0, 0); for (int i = 0; i < m; i++) { for (int j = 0; j < k; j++) { int mask = sta[j]; int ct = cont(i, mask); dp[i][mask][0] = ct; } } for (int i = 1; i < n; i++) { for (int ja = 0; ja < k; ja++) { int ct = cont(i, sta[ja]); for (int jb = 0; jb < k; jb++) { if (!(sta[ja] & sta[jb])) { for (int jc = 0; jc < k; jc++) { if (!(sta[ja] & sta[jc]) && !(sta[jb] & sta[jc])) { dp[i][sta[ja]][sta[jb]] = max(dp[i][sta[ja]][sta[jb]], dp[i-1][sta[jb]][sta[jc]] + ct); } } } } } } int ans = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < k; j++) { for (int l = 0; l < k; l++) { if (!(sta[j] & sta[l])) { ans = max(ans, dp[n - 1][sta[j]][sta[l]]); } } } } cout << ans << '\n';}signed main(){ ios::sync_with_stdio(0), cin.tie(0), cout.tie(0); int T = 1; // cin >> T; while (T--) solve(); return 0;}