萌新70pts求助

P2704 [NOI2001] 炮兵阵地

Proxima_Centauri @ 2024-03-22 22:09:14

rt,感谢各位大佬

#include <iostream>
#include <cstdio>
#include <algorithm>
using namespace std;
int h[110], p[110], b[110], cnt;
int f[110][110][110];
int main()
{
    int n, m;
    scanf("%d%d", &n, &m);
    for (int i = 0; i < (1 << m); i++)
    {
        if ((i & (i << 1)) || (i & (i << 2))) continue;
        p[++cnt] = i;
        int t = i;
        while (t)
        {
            b[cnt] += t & 1;
            t >>= 1;
        }
    }
    for (int i = 1; i <= n; i++)
        for (int j = 1; j <= m; j++)
        {
            char c;
            scanf(" %c", &c);
            h[i] <<= 1;
            h[i] += (c == 'H');
        }
    for (int j = 1; j <= cnt; j++)
    {
        if (p[j] & h[1]) continue;
        else f[1][j][1] = b[j];
    }
    for (int i = 2; i <= n; i++)
        for (int j = 1; j <= cnt; j++)
        {
            if (p[j] & h[i]) continue;
            for (int k = 1; k <= n; k++)
            {
                if (p[k] & h[i - 1]) continue;
                if (p[k] & p[j]) continue;
                for (int l = 1; l <= n; l++)
                {
                    if (p[l] & h[i - 2]) continue;
                    if (p[l] & p[k]) continue;
                    if (p[l] & p[j]) continue;
                    f[i][j][k] = max(f[i][j][k], f[i - 1][k][l] + b[j]);
                }
            }
        }
    int ans = 0;
    for (int j = 1; j <= cnt; j++)
        for (int k = 1; k <= cnt; k++) 
            ans = max(ans, f[n][j][k]);
    printf("%d\n", ans);
    return 0;
}

|