https://www.luogu.org/problemnew/show/P2704
知识点：1.滚动数组：取模实现
2.位运算优先级最低
顾是if(!(a&b))而不是if(!a&b)
code:
#include <bits/stdc++.h> #define N 101 #define M 10 using namespace std; int n,m; int tot = 0; int dp[4][1000][1000],mp[N],state[1000]; int val[1000]; int check(int k) { if(((k&(k<<1))==0)&&((k&(k<<2))==0)&&((k&(k>>1))==0)&&((k&(k>>2))==0))return 1; else return 0; } int get(int k) { int ans = 0; for(int i = 0;i < m;i++) { if(k&(1 << i))ans++; } return ans; } char ch[N]; int main() { scanf("%d%d",&n,&m); for(int i = 1;i <= n;i++) { scanf("%s",ch); for(int j = 0;j < m;j++) { if(ch[j] == 'H') { mp[i] = mp[i]|(1 << j); } } } for(int i = 0;i <= (1 << m) - 1;i++) { if(check(i)) { state[++tot] = i; val[tot] = get(i); dp[1][0][tot] = val[tot]; } } for(int i = 1;i <= tot;i++) { for(int j = 1;j <= tot;j++) { if((state[i]&state[j]) == 0&&(state[i]&mp[2]) == 0) dp[2][j][i] = max(dp[2][j][i],dp[1][0][j] + val[i]); } } for(int i = 3;i <= n;i++) { for(int j = 1;j <= tot;j++) if((state[j]&mp[i]) == 0) for(int k = 1;k <= tot;k++) if((state[k]&mp[i - 1]) == 0) for(int p = 1;p <= tot;p++) if((state[p]&mp[i - 2]) == 0) if((state[p]&state[k]) == 0 && (state[k]&state[j]) == 0 && (state[p]&state[j]) == 0) dp[i % 3][k][j] = max(dp[i % 3][k][j],dp[(i - 1) % 3][p][k] + val[j]); } int ans = -1; for(int i = 1;i <= tot;i++) for(int j = 1;j <= tot;j++) ans = max(dp[n % 3][j][i],ans); printf("%d",ans); return 0; }