WA10求调

#include <bits/stdc++.h>

using namespace std;

int n, m, ans, num, mp[1024], zt[1024], dp[105][1024][1024];
map<int, int> cnt;

int gs(int i)
{
    int cnt = 0;
    while(i)
    {
        if(i & 1)
        {
            cnt++;
        }
        i >>= 1;
    }
    return cnt;
}

signed main()
{
    cin >> n >> m;
    for (int i = 1; i <= n; i++) 
    {
        for (int j = 1; j <= m; j++)
        {
            int x;
            char c;
            cin >> c;
            x = (c == 'H');
            mp[i] <<= 1;
            mp[i] += x;
        }
    }

    for (int i = 1; i <= n; i++) 
    {
        cout << mp[i] << endl;
    }

    // cout << "a\n";
    for(int i = 0; i < (1 << m); i++)
    {
        if((!(i & (i << 1))) && (!(i & (i << 2))) && (!(i & (i >> 1))) && (!(i & (i >> 2))))
        {
            num++;
            zt[num] = i;
            cnt[i] = gs(i);
            if(!(zt[i] & mp[1]))
            {
                dp[1][zt[i]][0] = cnt[zt[i]];
            }
        }
    }
    // cout << "b\n";
    for(int i = 1; i <= num; i++)
    {
        if(!(zt[i] & mp[1]))
        {
            for(int j = 1; j <= num; j++)
            {
                if(!(zt[j] & mp[2]))
                {
                    if((zt[i] & zt[j]))
                    {
                        continue;
                    }
                    dp[2][zt[i]][zt[j]] = max(dp[2][zt[i]][zt[j]], dp[1][zt[j]][0] + cnt[zt[i]]);
                }
            }
        }
    }
    // cout << "c\n";
    for (int i = 3; i <= n; i++)
    {
        for (int j = 1; j <= num; j++)
        {
            if (!(zt[j] & mp[i]))
            {
                for (int k = 1; k <= num; k++)
                {
                    if (!(zt[k] & mp[i - 1]))
                    {
                        for(int l = 1; l <= num; l++)
                        {
                            if (!(zt[l] & mp[i - 2]))
                            {
                                if ((zt[j] & zt[k]) || (zt[j] & zt[l]) || (zt[k] & zt[l]))
                                {
                                    continue;
                                }
                                dp[i][zt[j]][zt[k]] = max(dp[i][zt[j]][zt[k]], dp[i - 1][zt[k]][zt[l]] + cnt[zt[j]]);
                            }
                        }
                    }
                }
            }
        }
    }
    // cout << "d\n";
    for (int i = 1; i <= num; i++)
    {
        for (int j = 1; j <= num; j++)
        {
            if(zt[i] & zt[j])
            {
                continue;
            }
            ans = max(ans, dp[n][zt[i]][zt[j]]);
        }
    }
    cout << ans;

    return 0;
}

提交记录