状压10pts求助

P2704 [NOI2001] 炮兵阵地

Dreamer_Boy @ 2023-05-27 21:26:35

#include <iostream>
#include <algorithm>

using namespace std;

int n, m;
const int N = 15, M = (1 << N) + 5;
char ch;
int f[N][N][3], a[110];
int sum[N];

int init(int x){
    int tot = 0;
    while(x){
        if(x & 1) tot ++ ;
        x >>= 1;
    }
    return tot;
}
int main()  
{
    cin >> n >> m;
    for (int i = 0 ;i < n;i ++ ){
        for (int j = 0; j < m;j ++ ){
            cin >> ch;
            a[i] <<= 1;
            if(ch == 'H') a[i] += 1;
            else a[i] += 0;
        }
    }
    for (int i = 0;i < (1 << m);i ++ ){
        sum[i] = init(i);
    }
    for (int s = 0 ;s < (1 << m); s ++ ){
        if(!(s & a[0] || (s & (s << 1) || (s & (s << 2))))){
            f[0][s][0] = sum[s];
        }
    }
    for (int l = 0; l < (1 << m); l ++ ){
        for(int s = 0; s < (1 << m); s ++ ){
            if(!((l & s) || (l & a[0]) || (s & a[1]) || (l & (l << 1)) || (l & (l << 2)) || (s & (s << 1)) || (s & (s << 2)) )){
                f[l][s][1] = sum[l] + sum[s];
            }
        }
    }
    for (int i = 2; i < n ;i ++ ){
        for (int l = 0; l < (1 << m); l ++ ){
            if(l & a[i - 1] || (l & (l << 1) || (l & (l << 2)))) continue;
            for(int s = 0; s < (1 << m); s ++ ){
                if(l & s || s & a[i] || (s & (s << 1)) || (s & (s << 2))) continue;
                for(int fl = 0; fl < (1 << m);fl ++ ){
                    if(fl & l || fl & s || fl & a[i-2] || (fl & (fl << 1)) || (fl & (fl << 2))) continue;
                    f[l][s][i % 3] = max(f[l][s][i % 3], f[fl][l][(i - 1) % 3] + sum[s]);
                }
            }
        }   
    }
    int ans = 0;
    for(int i = 0 ;i < (1 << m) ;i ++ ){
        for(int j = 0 ;j < (1 << m) ;j ++ ){
            ans = max(ans, f[i][j][(n - 1) % 3]);
        }
    }
    cout << ans << endl;
    return 0;
}

by __zhuruirong__ @ 2023-06-20 20:32:51

#include <iostream>
#include <algorithm>
using namespace std;

const int N = 110, M = 1 << 10;
int n, m;
int g[N];
int f[2][M][M];
vector<int> states, h[M];

bool check(int x) {
    return !(x & x >> 1 || x & x >> 2);
}

int count(int x) {
    int res = 0;
    for(int i = 0; i < m; i++)
        if(x >> i & 1) res++;
    return res;
}

int main() {

    cin >> n >> m;
    for(int i = 1; i <= n; i++)
        for(int j = 0; j < m; j++) {
            char ch;
            cin >> ch;
            if(ch == 'H') g[i] += 1 << j;
        } 

    for(int i = 0; i < 1 << m; i++)
        if(check(i)) states.push_back(i);

    for(auto x : states)
        for(auto y : states)
            if((x & y) == 0) h[x].push_back(y);

    for(int i = 1; i <= n + 2; i++)
        for(auto s : states)
            if(!(g[i] & s))
                for(auto x : h[s])
                    for(auto y : h[x])
                        if(!(s & y))
                            f[i&1][s][x] = max(f[i&1][s][x], f[i-1&1][x][y] + count(s));

    cout << f[n + 2 & 1][0][0] << endl;

    return 0;
}