胡言乱语:
没想到能够顺利地一遍A过这题,写发题解说说我的思路。
分析
首先因为炮的攻击距离是$2$,所以考虑到增多一维以刻画问题:
$$f_{i,u,v}$$表示已经放了前$i$行,其中第$i$行的状态是$u$,第$i-1$行的状态是$v$的所有情况中放置炮兵最大数。
因为第$i$行只受到它前面两行的影响,所以状态就由$f_{i-1,v,w}$转移而来($w$表示第$i-2$行的状态)
故有:
$$f_{i,u,v} = max(f_{i,u,v},f_{i-1,v,w}+状态u的炮兵数)$$
其他细节请看注释^3^
代码:
#include<bits/stdc++.h>
using namespace std;
const int N = 110, M = 1<<10;
int g[N];
int f[2][M][M];
int cnt[M];
int n,m;
vector<int> state;
bool check(int state){
if((state>>1)&state || (state>>2)&state || (state<<1)&state || (state<<2)&state) return false;
return true;
}
int cal(int state){
int res=0;
while(state){
state-=state&-state; //利用lowbit统计一个01串中1的个数
res++;
}
return res;
}
int main(){
cin>>n>>m;
for(int i=1;i<=n;i++)
for(int j=0;j<m;j++){
char ch; cin>>ch;
if(ch=='H') g[i]+=1<<j; //g[i]表示第i行地形对应的01串,其中1是山地
}
for(int i=0;i<1<<m;i++)
if(check(i)){
state.push_back(i); //储存合法状态
cnt[i]=cal(i);
}
for(int i=1;i<=n+2;i++)
for(int u=0;u<state.size();u++)
for(int v=0;v<state.size();v++)
for(int w=0;w<state.size();w++){
int c=state[u], b=state[v], a=state[w];
if(c&b || c&a) continue;
if(c&g[i]) continue;
f[i&1][u][v]=max(f[i&1][u][v],f[i-1&1][v][w]+cnt[c]);
}
cout<<f[n+2&1][0][0]<<endl;
return 0;
}
题外话:在提高课里看到y总写的代码有部分似乎可以删掉emmm
如下:
if (a & b | a & c | b & c) continue; ---> if (a & b | b & c) continue;
if (g[i] & b | g[i - 1] & a) continue; ---> if (g[i] & b ) continue;