题解 P2704 [NOI2001]炮兵阵地

· · 题解

我第一眼看到这道题就觉得是轮廓线dp（或者叫插头dp），结果AC后发现43篇题解没有一篇是轮廓线dp。。。

像这种往一个大方框里面填奇奇怪怪的形状，然后这个大方框有一边特别窄的难道不就是轮廓线dp么

首先，我们转换一下问题

1     X
2     X
3 X X X O O
4     O
5     O

对于十字，我们明显不需要去考虑 O 的部分，我们只需要关心 X 的部分会不会碰到其他十字的中心，

当然，这是按照从左往右从上往下的顺序枚举填充。

那么我们首先想到把上面的 1 2 3 行每个格子有没有十字中心状压掉，然后枚举当前位置要不要放十字，然后转移

要存十字中心这一行是因为十字中心左边部分也会被影响到

那么这个 dp 数组就可以这样开

f_{i,j,mask1,mask2,mask3}$ 表示 $(i,j)$ 位置当前行状态是 $mask1$ ，上一行状态是 $mask2$ ，上上行状态是 $mask3 ![](https://cdn.luogu.com.cn/upload/image_hosting/k5qh2z51.png) 假设我们现在枚举到绿色方格的位置，那么我们现在枚举的 3 行状态中，其实棕色部分是没有用的 所以我们可以把红色部分看成 1 行，粉色部分看成 1 行，然后这样就把 3 行的状态变成了 2 行 然后就是枚举绿色部分填不填十字， 分类讨论转移： ``` 1 2 3 4 5 ``` 5 是当前的位置： 如果 1 2 3 4 都是空的，那么可以在 5 上填十字或者不填 如果只有 1 3 是有十字中心或者只有 2 4 是有十字中心 ，那么只能不在 5 上填，因为用 2 个换 1 个得不偿失 如果只有 1 或只有 2 或只有 3 或只有 4 是有十字中心，那么可以选择在 5 上填十字或者不填 当然如果地形是 `H` 那就不能填 上面那张图转移完绿色的方格后轮廓线就会变成这样子：（即转移到的新状态） ![](https://cdn.luogu.com.cn/upload/image_hosting/g5sgdl19.png) 那么 $f_{i,j,mask1,mask2}$ 的前两位可以滚存掉 时间复杂度 $O(n\times m\times 2^{2m})

貌似不太行的亚子呢

我们可以非常容易地想到，这两行轮廓线的合法状态其实并不多

合法状态就是指这两行轮廓线状态中不存在冲突

我们可以直接通过dfs预处理搜出所有的合法状态，不到30000个

所以最后的时间复杂度大约是 O(n\times m\times 30000)，不开 O2 用 C++，最大点跑了 160ms，海星

// This code wrote by chtholly_micromaker(MicroMaker)
#include <bits/stdc++.h>
#define reg register
using namespace std;
template <class t> inline void read(t &s)
{
    s=0;
    reg int f=1;
    reg char c=getchar();
    while(!isdigit(c))
    {
        if(c=='-')
            f=-1;
        c=getchar();
    }
    while(isdigit(c))
        s=(s<<3)+(s<<1)+(c^48),c=getchar();
    s*=f;
    return;
}
char G[105][15];
int f[2][(1<<10)+5][(1<<10)+5];
int vis[3][10];
vector<pair<int,int> > Masks[11]; 
int n,m;
inline void checkmax(int &x,int y)
{
    if(x<y)
        x=y;
    return;
}
inline bool check(int pos)
{
    if(pos<m-1)
    {
        for(int i=0;i<3;++i)
            if(vis[i][pos]&&vis[i][pos+1])
                return false;
    }
    if(pos<m-2)
    {
        for(int i=0;i<3;++i)
            if(vis[i][pos]&&vis[i][pos+2])
                return false;
    }
    return true;
}
inline void dfs(int dep,int j,int mask1,int mask2)
{
    if(dep<0)
    {
        Masks[j].push_back(make_pair(mask1,mask2));
        return;
    }
    dfs(dep-1,j,mask1<<1,mask2<<1);
    if(dep<j)
        vis[1][dep]=true;
    else
        vis[0][dep]=true;
    if(check(dep))
        dfs(dep-1,j,mask1<<1|1,mask2<<1);
    if(dep<j)
        vis[1][dep]=false;
    else
        vis[0][dep]=false;
    if(dep<j)
        vis[2][dep]=true;
    else
        vis[1][dep]=true;
    if(check(dep))
    dfs(dep-1,j,mask1<<1,mask2<<1|1);
    if(dep<j)
        vis[2][dep]=false;
    else
        vis[1][dep]=false;
    return;
}
signed main(void)
{
    ios::sync_with_stdio(false);cin.tie(0);
    cin>>n>>m;
    for(int i=1;i<=n;++i)
        cin>>G[i];
    reg int full=(1<<m)-1;
    reg int fpos=0;
    reg int ans=0;
    for(int i=0;i<m;++i)
        dfs(m-1,i,0,0);
    for(int i=1;i<=n;++i)
        for(int j=0;j<m;++j)
        {
            for(int maskid=0;maskid<(int)Masks[j].size();++maskid)
            {
                reg int mask1=Masks[j][maskid].first,mask2=Masks[j][maskid].second;
                reg bool flg=false;
                reg bool l0=(j>0&&(mask2&(1<<(j-1)))),l1=(j>1&&(mask2&(1<<(j-2))));
                reg bool u0=mask1&(1<<j),u1=mask2&(1<<j);
                if(u0)
                {
                    if(!l0&&!l1&&G[i][j]=='P')
                        checkmax(f[fpos^1][mask1^(1<<j)][mask2|(1<<j)],f[fpos][mask1][mask2]);
                    flg=true;
                }
                if(u1)
                {
                    if(!l0&&!l1&&G[i][j]=='P')
                        checkmax(f[fpos^1][mask1^(1<<j)][mask2],f[fpos][mask1][mask2]);
                    flg=true;
                }
                if(l0)
                {
                    if(!u0&&!u1&&G[i][j]=='P')
                        checkmax(f[fpos^1][mask1][(mask2^(1<<(j-1)))|(1<<j)],f[fpos][mask1][mask2]);
                    flg=true;
                }
                if(l1)
                {
                    if(!u0&&!u1&&G[i][j]=='P')
                        checkmax(f[fpos^1][mask1][(mask2^(1<<(j-2)))|(1<<j)],f[fpos][mask1][mask2]);
                    flg=true;
                }
                checkmax(f[fpos^1][(mask1&(~(1<<j)))|(mask2&(1<<j))][mask2&(~(1<<j))],f[fpos][mask1][mask2]);
                if(flg||G[i][j]=='H')
                    continue;
                checkmax(f[fpos^1][(mask1&(~(1<<j)))|(mask2&(1<<j))][mask2|(1<<j)],f[fpos][mask1][mask2]+1);
            }
            for(int maskid=0;maskid<(int)Masks[j].size();++maskid)
                f[fpos][Masks[j][maskid].first][Masks[j][maskid].second]=0;
            fpos^=1;
        }
    for(int i=0;i<=full;++i)
        for(int j=0;j<=full;++j)
            checkmax(ans,f[fpos][i][j]);
    cout<<ans<<endl;
    return 0;
}