求助样例没过

xiaoyang222 @ 2024-06-15 20:45:45

by xiaoyang222 @ 2024-06-15 20:45:58

#include <iostream>
#include <vector>
using namespace std;
const int N=100+5,M=11;
int n,m;
int st[N];
int f[N][1<<M][1<<M];//上一行和这一行 
int popcount[1<<M];
vector<int> qwq;//合法的（这一行没有攻击的） 
bool check(int a,int b,int c){//是否会攻击 
    return (a&b) || (a&c) || (b&c);
}
bool check2(int a){
    return !((a&(a>>1)) || (a&(a>>2)));
}
int main(){
    ios::sync_with_stdio(false);
    cin.tie(0),cout.tie(0);
    cin >> n >> m;
    char c;
    for (int i=1;i<=n;++i){
        for (int j=0;j<m;++j){
            cin >> c;
            if (c=='P'){
                st[i]|=(1<<j);
            }
        }
    }
    for (int i=0;i<(1<<m);++i){
        if (check2(i)){
            qwq.emplace_back(i);
        }
        popcount[i]=popcount[i>>1]+(i&1);
    }
    for (int &s : qwq){
        if (s&st[1]) continue;
        f[1][0][s]=popcount[s];
    }
    for (int &s : qwq){
        if (s&st[1]) continue;
        for (int &t : qwq){
            if (t&st[2]) continue;
            if (check(s,t,0)) continue;
            f[2][s][t]=popcount[s]+popcount[t];
        }
    }
    for (int i=3;i<=n;++i){//直接从第三行开始 
        for (int &s : qwq){//这一行 
            if (s&st[i]) continue;
            for (int &t : qwq){//上一行 
                if (t&st[i-1]) continue;
                for (int &qaq : qwq){//上上一行 
                    if (qaq&st[i-2]) continue;
                    if (check(s,t,qaq)) continue;
                    f[i][t][s]=max(f[i][t][s],f[i-1][qaq][t]+popcount[s]);
                }
            }
        }
    }
    int ans=0;
    for (int &s : qwq){
        for (int &t : qwq){
            ans=max(ans,f[n][s][t]);
        }
    }
    cout<<ans<<endl;
    return 0;
}

by xiaoyang222 @ 2024-06-15 20:46:42

过了过了

by xiaoyang222 @ 2024-06-15 20:47:31

史上最快结帖，发现 H 是山地，我把 P 看出山地了

by jeffstart @ 2024-06-15 23:23:13

@xiangyang222 为啥你每次发求助帖最后都是自己解决啊。

冥冥之中，自由天意

@xiaoyang222 @xiaoyang222 @xiaoyang222 @xiaoyang222