提莫队长正在待命(DP)

提莫队长正在待命
Problem:J
Time Limit:2000ms
Memory Limit:65536K
Description
“整装待发！”

遥远的瓦罗兰大陆上，有一座神秘的城池——班德尔城，班德尔城的历史非常悠久，其主要居民都是身高1m左右的约德尔人。而保卫这座城池安全的正是班德尔城最富盛名的特种部队之一“主舰斥候队”。提莫队长正是斥候队的侦查兵首领。凭借一手“致盲吹箭”和久负盛名的“小莫快跑”，提莫队长可攻可守，击退了无数试图进犯班德尔城的敌人。
但是众所周知，真正使他在瓦罗兰大陆上声名鹊起，令无数豪杰闻之而胆颤的是他的蘑菇。
但是因为这是一个算法题，而不是一场故事会。所以你需要帮助提莫队长解决一个困扰了他很久的问题。
给定一个长为n，宽为m的区域。这一片区域上由各种地形组成。其中包括
陆地，用大写字符“L”表示
水面，用大写字符“W”表示
森林，用大写字符“F”表示
城池，用大写字符“C”表示
提莫队长需要在这片区域上布置他的蘑菇来抵御随时可能进犯的敌人。
为了更好的隐蔽他的蘑菇只能被种在森林区域。
并且因为蘑菇存在可能爆炸的风险，所以不能够将一个蘑菇种在另一个蘑菇的爆炸范围内。
同时为了保证城池的安全，每座城池也均不能在蘑菇的爆炸范围内
每一个蘑菇的攻击范围包含其上下左右四个方向和自身共计9个单位区域内。

如图1这样一个区域内，提莫只能在F内种下蘑菇
如图2在(2,3)种下一个蘑菇，红色区域即为蘑菇的攻击范围
（手动分割线）
现在请你帮助提莫队长安排一个最优方案以便在这片区域内能够种下最多的蘑菇，来抵御敌人的入侵，守护班德尔城的安宁
Input
第一行两个整数n，m 1<=n<=100,1<=m<=10
接下来n行为区域的分布，保证不含有除“LWFC”外的任何字符
upd:第六组数据已经修复
出题人诚恳谢罪https://acm.njupt.edu.cn/pb/srz6TT
Output
一个整数，代表提莫队长能够在这片区域内种下的最多的蘑菇
Sample Input
5 4
FLFF
FFLL
FFFF
FLFF
FLLF
Sample Output
6
Hint
请注意本题的时空限制，做适当的优化
#pragma GCC optimize(2)
请给程序在头文件前加上如上的预编译优化指令

#pragma GCC optimize(2)
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
char district[105][15];
int dp[5][1100][1100]; //到第i行，第i行状态为j，上一行状态为k,同时考虑每一行只与上两行有关所以滚动数组优化
bool chksg[105][1100];
bool chkdual[1100][1100];
int n, m, maxm, ans = 0;
bool chka(int line, int sit) //检查当前行状态是否合法
{
    //不可以放在除森林以外的任何地方并且需要满足彼此间隔大于等于3
    int las = -1;
    for (int i = 0; i < m; i++)
    {
        if (((sit >> i) & 1) == 1)
        {
            if (las == -1) //直接更新
            {
                las = i;
            }
            else
            {
                if (i - las < 3)
                {
                    return false;
                }
                else
                {
                    las = i;
                }
            }
            if (district[line][m - i] != 'F')
            {
                return false;
            }
        }
    }
    return true;
}
bool chkb(int down, int up) //检查两行蘑菇之间是否会冲突
{
    int nt = (up & down);
    return nt == 0;
}
void init() //预处理情况
{
    for (int i = 1; i <= n; i++)
    {
        for (int j = 0; j <= maxm; j++)
        {
            chksg[i][j] = chka(i, j);
        }
    }
    for (int i = 0; i <= maxm; i++)
    {
        for (int j = 0; j <= maxm; j++)
        {
            chkdual[i][j] = chkb(i, j);
        }
    }
}
int main()
{
    //freopen("","r",stdin);
    //freopen("","w",stdout);
    cin >> n >> m;
    maxm = ((1 << m) - 1);
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            cin >> district[i][j];
        }
    }
    for (int i = 1; i <= n; i++)
    {
        for (int j = 1; j <= m; j++)
        {
            if (district[i][j] == 'C')
            {
                for (int p = -2; p <= 2; p++) //考虑将城池的范围直接更改为不可放置即可
                {
                    if (i + p >= 1 && i + p <= n)
                    {
                        district[i + p][j] = 'L';
                    }
                    if (j + p >= 1 && j + p <= m)
                    {
                        district[i][j + p] = 'L';
                    }
                }
            }
        }
    }
    //预处理chk的情况
    init();
    //考虑第一行只要合法就直接放
    for (int i = 0; i <= maxm; i++)
    {
        if (chksg[1][i])
        {
            dp[1 % 2][i][0] = __builtin_popcount(i);
        }
    }
    //考虑第二行只要不与第一行冲突就可以直接放
    for (int i = 0; i <= maxm; i++)
    {
        if (chksg[2][i])
        {
            for (int j = 0; j <= maxm; j++)
            {
                if (chksg[1][j] && chkdual[i][j])
                {
                    dp[2 % 2][i][j] = dp[1 % 2][j][0] + __builtin_popcount(i);
                }
            }
        }
    }
    //之后情况
    for (int i = 3; i <= n; i++)
    {
        for (int j = 0; j <= maxm; j++) //枚举当前行情况
        {
            if (chksg[i][j]) //检查当前行是否合法
            {
                int cnt = (int)__builtin_popcount(j);
                for (int k = 0; k <= maxm; k++) //枚举上一行情况
                {
                    if (chksg[i - 1][k] && chkdual[j][k]) //检查上一行状态是否合法并且是否会与当前行冲突
                    {
                        for (int p = 0; p <= maxm; p++) //枚举上上一行情况
                        {
                            if (chkdual[j][p]) //检查上上一行与当前行是否冲突
                            {
                                dp[i % 2][j][k] = max(dp[i % 2][j][k], dp[(i - 1) % 2][k][p] + cnt);
                                if (i == n)
                                {
                                    ans = max(ans, dp[i % 2][j][k]);
                                }
                            }
                        }
                    }
                }
            }
        }
    }
    cout << ans << endl;
    return 0;
}