萌新刚学OI,奇怪subtask 1WA5个点

P2704 [NOI2001] 炮兵阵地

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
我排除无效情况的时候好像忘记改统计了...


|