公元某年的猫 @ 2018-05-07 18:24:01
#include<cstdio>
#include<iostream>
#include<string>
using namespace std;
const int N = 101, M = 11;
int n, m, cnt, ans, num[1<<M], state[1<<M], dp[N][1<<M][1<<M];
string map[N];
int get_num(int x) {
int count = 0;
while (x) {
if (x&1) count++;
x>>=1;
}
return count;
}
void init() {
int i, j, MAX = 1<<m;
for (i = 0; i < MAX; i++) {
if (i&(i<<1) || i&(i<<2) || i&(i>>1) || i&(i>>2)) continue;
else {
state[++cnt] = i;
num[cnt] = get_num(i);
}
}
return ;
}
bool judge(int cur, int s) {
int i, l = map[cur].size();
for (i = l-1; i >= 0; i--) {
if (map[cur][i] == 'H' && s&1) return false;
s>>=1;
}
return true;
}
int main() {
int i, j, k, l, p;
scanf("%d%d", &n ,&m);
for (i = 1; i <= n; i++)
cin >> map[i];
init();
for (i = 1; i <= cnt; i++) {
if (!judge(1, state[i])) continue;
dp[1][i][0] = num[i];
}
for (i = 1; i <= cnt; i++) {
if (!judge(2, state[i])) continue;
for (j = 1; j <= cnt; j++) {
if (!judge(1, state[j])) continue;
if (state[i]&state[j]) continue;
dp[2][i][j] = dp[1][j][0] + num[i];
}
}
for (i = 3; i <= n; i++) {
for (j = 1; j <= cnt; j++) {
if (!judge(i, state[j])) continue;
for (k = 1; k <= cnt; k++) {
if (!judge(i-1, state[k])) continue;
if (state[k]&state[j]) continue;
for (l = 1; l <= cnt; l++) {
if (!judge(i-2, state[l])) continue;
if (state[l]&state[k] || state[l]&state[j]) continue;
dp[i][j][k] = dp[i-1][k][l] + num[j];
ans = max(dp[i][j][k], ans);
}
}
}
}
printf("%d", ans);
return 0;
}
by soy_un_perro @ 2018-05-07 18:45:14
用你的程序在洛谷IDE用样例试了一下,RE,至于原因,本蒟蒻太弱,请dalao自己找。
by Scarlet_Lightning @ 2018-05-07 19:54:35
有可能出现Windows下正常的内存泄漏,到Linux下就不行了(别太信,我是瞎说的)
by Scarlet_Lightning @ 2018-05-07 19:55:22
@xzsdcpp 你这图片像素真高Orz。。。。。
by soy_un_perro @ 2018-05-07 19:56:19
为了上传,呵呵
by 公元某年的猫 @ 2018-05-07 21:45:52
@王瑞 好的好的,感谢大佬
by 公元某年的猫 @ 2018-05-07 21:47:12
@xzsdcpp 好吧,感谢大佬的提醒
by 公元某年的猫 @ 2018-05-07 22:12:49
已AC //好吧,其实就是M多开了1,没想到直接全炸了。
by 四方契 @ 2018-07-18 20:29:26
友情提示:luogu上MLE和RE经常混。。