Minakami_Yuki @ 2019-09-05 09:40:38

by Minakami_Yuki @ 2019-09-05 09:41:15

源代码：（我不是故意要用大标题的...）

#include <cstdio>
#include <cstring>
#include <cctype>

inline int read() {
    char ch = getchar(); int r = 0, w = 1;
    while(!isdigit(ch)) {if(ch == '-') w = -1; ch = getchar();}
    while(isdigit(ch)) {r = r * 10 + ch - '0', ch = getchar();}
    return r * w;
}

void print2(int x, int len) {
    if(len) {
        print2(x >> 1, len - 1);
        printf("%d", x & 1);
    }
}

const int N = 11;

int n, m, ans = 0;
int cant[101], dp[1 << N][1 << N][3], s[1 << N];

void dfs(int sit, int sum, int now) {
    if(now >= m) {
        s[sit] = sum;
        return;
    }
    dfs(sit + (1 << now), sum + 1, now + 1);
    dfs(sit, sum, now + 1);
}

inline int max(int a, int b) {return a > b ? a : b;}

int main() {
    n = read(), m = read();
    dfs(0, 0, 0);
    for(register int i = 0; i < n; i++) {
        for(register int j = 0; j < m; j++) {
            cant[i] = (cant[i] << 1) + (getchar() == 'H');
        }
        getchar();
    }
    for(register int i = 0; i < (1 << m); i++) 
        if(!((i & cant[0]) || (i & (i << 1)) || (i & (i << 2))))
            dp[0][i][0] = s[i];
    for(register int i = 0; i < (1 << m); i++) {
        for(register int j = 0; j < (1 << m); j++) {
            if(!((i & j) || (i & cant[0]) || (i & (i << 1)) || (i & (i << 2)) || (j & cant[1]) || (j & (j << 1)) || (j & (j << 2)))) {
                dp[i][j][1] = s[i] + s[j];
            }
        }
    }
    for(register int i = 2; i < n; i++) {
        for(register int j = 0; j < (1 << m); j++) {
            if((j & (cant[i - 1])) || (j & (j << 1)) || (j & (j << 2))) continue;
            for(register int k = 0; k < (1 << m); k++) {
                if((k & cant[i]) || (j & k) || (k & (k << 1)) || (k & (k << 2))) continue;
                for(register int S = 0; S < (1 << m); S++) {
                    if((S & j) || (S & k) || (S & cant[i - 2]) || (S & (S << 1)) || (S & (S << 2))) continue;
                    dp[j][k][i % 3] = max(dp[j][k][i % 3], dp[S][j][(i - 1) % 3] + s[k]);
                }
            }
        }
    }
    for(register int i = 0; i < (1 << m); i++) {
        for(register int j = 0; j < (1 << m); j++) {
            ans = max(ans, dp[i][j][(n - 1) % 3]);
        }
    }
    printf("%d\n", ans);
    return 0;
}

by pzc2004 @ 2019-09-05 09:41:53

请不要质疑一道通过4.67k的题目

by Minakami_Yuki @ 2019-09-05 09:43:18

@WEMS_pzc 没有质疑谢谢，只是好奇为什么luogu没过样例

by By_Ha @ 2019-09-05 10:21:47

你去UOJ自定义测试下

by Minakami_Yuki @ 2019-09-05 10:33:33

@By_Ha 把 getchar() 换了，现在 \mathrm A 了

by 黑星 @ 2019-09-05 20:41:40

我也是这样，改成cin就错了，蒟蒻想问为什么

by 黑星 @ 2019-09-05 21:56:43

@黑星 前面的n和m是用cin读入的，但是在读每一行的时候，都提前打了个getchar读完了换行，玄学？

by nebulyu @ 2020-01-13 20:16:46

同问

by 九思 @ 2020-01-14 17:29:59

@qazc @黑星 @Minagami_Yuki luogu提交永远不要用getchar()不要问为什么:)

by 九思 @ 2020-01-14 17:30:23

用就是寻死