fast_photon @ 2022-02-08 17:22:59
#include<cstdio>
#include<iostream>
#include<cstring>
using namespace std;
int lib[65], ln;
int dp[5][65][65], n, m, cnt;
int map[105];
char ch;
int tot(int x) {
int cntt = 0;
while(x > 0) {
cntt += (x & 1);
x >>= 1;
}
return cntt;
}
int main() {
scanf("%d %d", &n, &m);
for(int i = 0; i < (1 << m); i++) {
if(!(i & (i << 1)) && !(i & (i << 2))) {
lib[ln++] = i;
//cout << i << endl;
}
}
for(int i = 0; i < n; i++) {
for(int j = 0; j < m; j++) {
map[i] <<= 1;
cin >> ch;
if(ch == 'H') map[i]++;
}
//cout << map[i] << endl;
for(int j = 0; j < ln; j++) {
for(int k = 0; k < ln; k++) {
dp[i & 1][j][k] = 0;
}
}
for(int j = 0; j < ln; j++) {//上行
if(i) if(lib[j] & map[i - 1]) continue;
for(int k = 0; k < ln; k++) {//上上行
if(i >= 2) if(lib[k] & map[i - 2]) continue;
if(lib[j] & lib[k]) continue;
for(int l = 0; l < ln; l++) {//本行
if(lib[l] & map[i] || lib[l] & lib[j] || lib[l] & lib[k]) continue;
dp[i & 1][l][j] = max(dp[1 - (i & 1)][j][k] + tot(lib[l]), dp[i & 1][l][j]);
//cout << i << ' ' << l <<' ' << j << ' ' << dp[i & 1][l][j] << endl;
}
}
}
for(int j = 0; j < ln; j++) {
for(int k = 0; k < ln; k++) {
if(!(j & k))cnt = max(cnt, dp[i & 1][j][k]);
}
}
}
printf("%d\n", cnt);
}
by Technablode @ 2022-02-08 18:36:05
这像是个刚学OI的人能写出来的代码吗
by Technablode @ 2022-02-08 18:36:29
%%%
by cookiebus @ 2022-02-08 21:45:02
楼主这种小可爱,那就我来看看吧。。。
by cookiebus @ 2022-02-08 21:50:08
if(!(j & k))cnt = max(cnt, dp[i & 1][j][k]);
应该改成
if(!(lib[j] & lib[k]))cnt = max(cnt, dp[i & 1][j][k]);
然后就能AC
by fast_photon @ 2022-02-08 21:54:10
@cookiebus
emmmm谢谢cls
我排除无效情况的时候好像忘记改统计了...