30pts求调

#include<bits/stdc++.h>
using namespace std;
int n, m, ans;
int f[4][1100][1100], plan[114];// f:[row][nowline][lastline];

bool checkrow(int i, int r) {return !(i & (i << 2)) && !(i & (i << 1)) && ((plan[r] | i) == plan[r]);}

bool checkcol(int now, int lst, int llst) {return !(now & lst) && !(now & llst) && !(lst & llst);}

int main()
{
    cin >> n >> m;
    // if(n == 5 && m == 4) return cout << 6 << endl, 0;
    if(n == 1)
    {
        cout << (m / 3 > 0 ? m / 3 : 1) << endl;
        return 0;
    }
    getchar();
    for(int i = 1; i <= n; i++)
    {
        for(int j = 1; j <= m; j++)
        {
            char x = getchar();
            plan[i] *= 2;
            plan[i] += (x == 'P' ? 1 : 0);
        }
        getchar();
        // cout << plan[i] << endl;
    }
    for(int i = 1; i < (1 << m); i++)
    {
        if(checkrow(i, 1)) f[1][i][0] = max(f[1][i][0], __builtin_popcount(i));
        for(int j = 1; j < (1 << m); j++)
        {
            if(checkrow(j, 2) && checkcol(i, j, 0)) f[2][j][i] = max(f[2][j][i], f[1][i][0] + __builtin_popcount(j));
            if(n == 2) ans = max(ans, f[2][j][i]);
            // cout << 2 << ' ' << i << ' ' << j << ' ' << f[2][j][i] << endl;
        }
        // cout << 1 << ' ' << i << ' ' << f[1][i][0] << endl;
    }
    if(n == 2)
    {
        cout << ans << endl;
        return 0;
    }
    // cout << checkrow(9) << endl;
    for(int i = 3; i <= n; i++)
    {
        for(int j = 0; j < (1 << m); j++)
        {
            if(!checkrow(j, i - 2)) continue;
            for(int k = 0; k < (1 << m); k++)
            {
                if(!checkrow(k, i - 1) || !checkcol(k, j, 0)) continue;
                for(int l = 0; l < (1 << m); l++)
                {
                    // if(i == 4 && l == 9) cout << checkrow(l, i) << ' ' << checkcol(l, k, j) << endl;
                    if(!checkrow(l, i) || !checkcol(l, k, j)) continue;
                    // if(l == 9) cout << '!';
                    f[3][l][k] = max(f[3][l][k], f[2][k][j] + __builtin_popcount(l));
                    // if(i == 4) cout << i << ' ' << j << ' ' << k << ' ' << l << ' ' << f[i][l][k] << endl;
                }
            }
        }
        memcpy(f[1], f[2], sizeof(f[2]));
        memcpy(f[2], f[3], sizeof(f[3]));
    }
    for(int i = 0; i < (1 << m); i++)
    {
        if(!checkrow(i, n - 1)) continue;
        for(int j = 0; j < (1 << m); j++)
        {
            if(!checkrow(j, n) || !checkcol(j, i, 0)) continue;
            // cout << j << ' ' << i << ' ' << f[3][i][j] << endl;
            ans = max(ans, f[3][i][j]);
        }
    }
    cout << ans << endl;
    return 0;
}

50 10
PPHPPHPPPP
PPPHPPPHPP
PHPPPHPPPH
PHPHHHHPPH
PPPPPPPPPH
PPPHPPHPPP
PHPPPPPHPH
HPHPPPPPPP
PPPHPHPPPP
HHHHPPPHHP
PPPHPPPHHP
PPPHPPPPHP
PPHHHPHPHP
PPHPHPPPHP
HHPPPPPPPP
HPPPPPHPPH
PPHPPPHPHH
HHHPHHPHPP
PPPHHPHPPH
HHPPPHPPHH
HPPPPPPHHH
PPPPHHPPPP
HPHPPPHPPH
PPPPPPPHPP
HPPPPPPPHP
HPPPPHPHHH
PHHHPHHPHP
PPPPPPPHPH
HPPPPHHPPP
PPPPPPHHHH
HPHPHHPPPH
PHPHHPPPPH
PHHPHHPPPH
HHPPPPPHHP
HPHPHPPHHP
PPHPHPPHPH
PHHPPPPPPH
PHHPHPHHHH
PHPHHPPPPP
PPHHPPPHHP
PPPPHPPHPH
PHPPPPHPHH
PPPPPHHHPP
PPPHPHHPHP
PPHPPPHHHP
PPHPPPPHHH
PHPPPPHPHP
HPPPPHPPHP
PPPPPPHHPH
PPHHHPPPPP