链接
https://loj.ac/p/10173
题意
矩阵中有山和平地,只能在平地上放置炮兵,炮兵的射程为上下左右两格内。
必须保证所有炮兵不在别的炮兵射程内。
求最大放置炮兵数。
思路
根据题意每行或每列两个炮兵必须相隔两格。
先预处理一行放置炮兵的所有情况,用二进制保存状态,当 $m=10$ 时,合法的只有 $60$ 种状态。
记 $dp_{i,j,k}$ 为第 $i$ 行为 $j$ 状态,$i-1$ 行为 $k$ 状态的最大放置数:
$dp_{i,j,k}=\max(dp_{i-1,k,z})$
转移时需要判断每行放置炮兵的位置是否有山以及 $x,y,z$ 是否两两合法。
同样用二进制保存山的状态,存在山的位置为 $1$,显然当两个状态按位与的值非 $0$ 时,这两个状态不能共存。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56
| #include <bits/stdc++.h> #define SZ(x) (int)(x).size() #define ALL(x) (x).begin(),(x).end() #define PB push_back #define EB emplace_back #define MP make_pair #define FI first #define SE second using namespace std; typedef double DB; typedef long double LD; typedef long long LL; typedef unsigned long long ULL; typedef pair<int,int> PII; typedef vector<int> VI; typedef vector<PII> VPII;
const int N=105; int n,m,dp[N][N*10][N*10],tot[N*10],st[N*10]; set<int> s; void dfs(int pos,int t,int d) { s.insert(t); tot[t]=d; for(int i=pos+3;i<m;i++) dfs(i,t|(1<<i),d+1); } bool check(int i,int j,int a,int b) { if(j<=0) return true; if(a&st[i]||b&st[j]||a&b) return false; return true; } int main() { ios::sync_with_stdio(false); cin.tie(nullptr); cin>>n>>m; for(int i=1;i<=n;i++) for(int j=0;j<m;j++) { char c; cin>>c; if(c=='H') st[i]|=1<<j; } dfs(-3,0,0); for(int i=1;i<=n;i++) for(auto x:s) for(auto y:s) { if(!check(i,i-1,x,y)) continue; for(auto z:s) if(check(i,i-2,x,z)&&check(i-1,i-2,y,z)) dp[i][x][y]=max(dp[i][x][y],dp[i-1][y][z]+tot[x]); } int res=0; for(auto x:s) for(auto y:s) res=max(res,dp[n][x][y]); cout<<res<<'\n'; return 0; }
|