洛谷2704 [NOI2001]炮兵阵地

题意

在 $N\times M$ 的图中部署炮兵，只有平原才能部署。每个炮兵的攻击范围为上下左右各延申两格，求方案数。

其中 $N\le 100,M\le 10$ 。

题解

跟 玉米田 差不多，但是因为前两行都对当前状态有影响，所以需要多一维。

如果直接开 $\text{f}[105][1024][1024]$ 的数组空间就爆了，所以需要预处理每一行合法的状态。可以发现合法的状态最多 $60$ 种，所以开 $\text{f}[105][65][65]$ 就够了。

$$\text{f}[i][k][j]=max(\text{f}[i][k][j],\text{f}[i-1][l][k]+\text{num}[j])$$

其中 $\text{num}[j]$ 表示状态 $j$ 中包含的 $1$ 的个数。

#include<bits/stdc++.h>

using namespace std;

inline int read()
{
    char ch=getchar();
    int f=1,x=0;
    while (ch<'0' || ch>'9')
    {
        if (ch=='-') f=-1;
        ch=getchar();
    }
    while (ch>='0' && ch<='9')
    {
        x=x*10+ch-'0';
        ch=getchar();
    }
    return f*x;
}

int n,m,M,cnt,ans,f[105][65][65],ok[65],s[105],num[65];

inline int get_1(int x)
{
    int ans=0;
    while (x) x&=x-1,ans++;
    return ans;
}

int main()
{
    n=read(); m=read();
    for (int i=1;i<=n;i++)
    {
        char ch[15];
        scanf("%s",ch+1);
        int len=strlen(ch+1);
        for (int j=1;j<=len;j++) s[i]=(s[i]<<1)+(ch[j]=='P');
    }
    M=1<<m;
    for (int i=0;i<M;i++)
    {
        if (i&(i<<1) || i&(i<<2)) continue;
        ok[++cnt]=i;
        num[cnt]=get_1(i);
        if ((i&s[1])==i) f[1][0][cnt]=num[cnt];
    }
    for (int i=1;i<=cnt;i++)
    {
        for (int j=1;j<=cnt;j++)
        {
            if ((ok[j]&s[2])!=ok[j] || ok[i]&ok[j]) continue;
            f[2][i][j]=f[1][0][i]+num[j];
        }
    }
    for (int i=3;i<=n;i++)
    {
        for (int j=1;j<=cnt;j++) //now
        {
            if ((ok[j]&s[i])!=ok[j]) continue;
            for (int k=1;k<=cnt;k++) //last
            {
                if (ok[j]&ok[k]) continue;
                for (int l=1;l<=cnt;l++)
                {
                    if ((ok[j]&ok[l]) || (ok[k]&ok[l])) continue;
                    f[i][k][j]=max(f[i][k][j],f[i-1][l][k]+num[j]);
                }
            }
        }
    }
    for (int i=1;i<=cnt;i++) for (int j=1;j<=cnt;j++) ans=max(ans,f[n][i][j]);
    printf("%d",ans);
    return 0;
}