题解 P2337 【[SCOI2012]喵星人的入侵】

UltiMadow · 2020-04-17 10:53:29 · 题解

本题解思路&部分代码实现来自这篇日报

终于过了，调了3h，写个题解纪念一下

这道题让我感到了什么叫真正的毒瘤

这题呢，看一眼数据范围，大概是插头dp

那我们就要考虑如何设计状态了

显然，本题中只记录轮廓线的插头状态是不够的，因为每个点的权值是由它周围的八个点的状态决定的，所以我们还要记录轮廓线的路径，也就是轮廓线上是放障碍还是炮台还是路径

我们记轮廓线上如果是障碍则为状态 0，如果是路径则为状态 1，如果是炮台则为 3

当然，我们发现插头状态仅记录左括号（记为1），右括号（记为2），和无插头（记为0）是不够的，因为本题中可能有没有括号和它匹配的插头，我们称其为独立插头（记为3）

我们又发现炮台的数量还有个限制，于是还要加一个状态记录炮台的数量

接下来，就是喜闻乐见的大力分类讨论时间啦

（当然，如果你没有做过这个题，那么建议你先去做一下，因为本题插头使用括号表示法）

我们记 pl1 为右插头，记 pl2 为下插头

1. 这个点 pl1=0 且左边是路径或 pl2=0 且上边是路径
   这种情况显然需要用障碍去堵住
   那么，显然只有无左插头且无下插头的情况是合法的
   接下来，只要转移这个点放炮台或障碍就行了

2. 这个点是障碍点
   这应该是最简单的一种
   显然只有无左插头且无下插头的情况是合法的
   直接转移即可

3. 这个点是非障碍点
   （疯狂的地方开始了）
   1）若 pl1=0 且 pl2=0

   2）若 $pl1=0$ 或 $pl2=0 3）若 $pl1=1$ 且 $pl2=1 4）若 $pl1=2$ 且 $pl2=2 5）若 $pl1=1$ 且 $pl2=2 6）若 $pl1=2$ 且 $pl2=1 7）若 $pl1=1$ 且 $pl2=3$ 或 $pl1=3$ 且 $pl2=1 8）若 $pl1=2$ 且 $pl2=3$ 或 $pl1=3$ 且 $pl2=2 9）若 $pl1=3$ 且 $pl2=3

4. 这个点是起点或者终点
   1）若 pl1=0 且 pl2=0

   2）若 $pl1=1$ 且 $pl2=0$ 或 $pl1=0$ 且 $pl2=1 3）若 $pl1=2$ 且 $pl2=0$ 或 $pl1=0$ 且 $pl2=2 4）若 $pl1=3$ 且 $pl2=0$ 或 $pl1=0$ 且 $pl2=3

以上是大力分类

接下来，我们来讲讲点权的事情

如果经过这个点，由于我们只知道轮廓线上的周围四个点的情况，所以只能加上这四个点中炮台的个数

如果这个点放障碍，不加，直接传下去就行

如果这个点放炮台，我们就要加上轮廓线上路径的个数，那为啥这样直接加是对的呢？

我们如果不经过一个点，我们可以直接把它设置成障碍，这样，一个炮台的贡献就是轮廓线上的周围四个点中路径的个数

该解释的都解释了，我们来看代码吧

#include<bits/stdc++.h>
#define MAXN 25
#define p 100007
#define int long long
using namespace std;
int n,m,K,now,pre;
char c[MAXN][MAXN];
int head[p+3],nxt[1<<24];
int f[2][1<<24],fst[2][3][1<<24];
int cnt[2];
void insert(int state1,int state2,int state3,int val)
{
    int ha=((((1ll*state1<<16)|state2)<<4)|state3)%p+1;//哈希
    for(int i=head[ha];i;i=nxt[i])
        if(fst[now][0][i]==state1&&fst[now][1][i]==state2&&fst[now][2][i]==state3)
        {
            f[now][i]=max(f[now][i],val);
            return;
        }
    f[now][++cnt[now]]=val;
    fst[now][0][cnt[now]]=state1;
    fst[now][1][cnt[now]]=state2;
    fst[now][2][cnt[now]]=state3;//三个状态
    nxt[cnt[now]]=head[ha];
    head[ha]=cnt[now];
}//hash表
int left(int state,int pos,int val)
{//向左寻找左括号
    int tot=1;
    while(true)
    {
        int pl=(state>>(pos<<1))&3;
        if(pl==2)tot++;if(pl==1) tot--;
        if(!tot)return state^(pl<<(pos<<1))^(val<<(pos<<1));
        pos--;
    }
}
int right(int state,int pos,int val)
{//向右寻找右括号
    int tot=1;
    while(true)
    {
        int pl=(state>>(pos<<1))&3;
        if(pl==1)tot++;if(pl==2) tot--;
        if(!tot)return state^(pl<<(pos<<1))^(val<<(pos<<1));
        pos++;
    }
}
char tmp[MAXN][MAXN];
signed main()
{
    scanf("%lld%lld%lld",&n,&m,&K);
    for(int i=0;i<n;i++)scanf("%s",c[i]);
    if(n<m)
    {//n<m的时候把地图转90度
        memcpy(tmp,c,sizeof(c));
        for(int i=0;i<n;i++)
            for(int j=0;j<m;j++)
                c[j][i]=tmp[i][j];
        swap(n,m);
    }
    cnt[0]=1;
    for(int i=0;i<n;i++)
    {
        for(int j=1;j<=cnt[now];j++)
            fst[now][0][j]<<=2;
        for(int j=1;j<=cnt[now];j++)
            fst[now][1][j]=(fst[now][1][j]^(((fst[now][1][j]>>(m+1<<1))&3)<<(m+1<<1)))<<2;//更新上一行的状态
        for(int j=0;j<m;j++)
        {
            pre=now;now^=1;cnt[now]=0;
            memset(head,0,sizeof(head));//注意初始化
            for(int k=1;k<=cnt[pre];k++)
            {
                int sta=fst[pre][0][k],stb=fst[pre][1][k],stc=fst[pre][2][k];
                int val=f[pre][k];
                if(sta>=(1<<(m+1<<1)))continue;
                int pl1=(sta>>(j<<1))&3;//right
                int pl2=(sta>>(j+1<<1))&3;//down
                int r=(stb>>(j<<1))&3;//右状态
                int ur=(stb>>(j+1<<1))&3;//右上状态
                int u=(stb>>(j+2<<1))&3;//上状态
                int ul=(stb>>(j+3<<1))&3;//左上状态
                int now=(sta^(pl1<<(j<<1))^(pl2<<(j+1<<1)));
                if((!pl1&&r==1)||(!pl2&&u==1))//1
                {
                    if(pl1||pl2)continue;
                    insert(now,stb^(ur<<(j+1<<1)),stc,val);//放障碍
                    if(stc<K&&c[i][j]=='.')
                        insert(now,stb^(ur<<(j+1<<1))^(3<<(j+1<<1)),stc+1,val+(r==1)+(ur==1)+(u==1)+(ul==1));//放炮台
                }
                else if(c[i][j]=='#'){if(!pl1&&!pl2)insert(now,stb^(ur<<(j+1<<1)),stc,val);}//2
                else if(c[i][j]=='.')//3
                {
                    if(!pl1&&!pl2)//1)
                    {
                        if(stc<K)
                            insert(now,stb^(ur<<(j+1<<1))^(3<<(j+1<<1)),stc+1,
                                val+(r==1)+(ur==1)+(u==1)+(ul==1));//放炮台
                        insert(now^(1<<(j<<1))^(2<<(j+1<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
                            val+(r==3)+(ur==3)+(u==3)+(ul==3));//走
                        insert(now,stb^(ur<<(j+1<<1)),stc,val);//不走
                    }
                    else if(!pl1&&pl2)//2）
                    {
                        insert(now^(pl2<<(j<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
                            val+(r==3)+(ur==3)+(u==3)+(ul==3));
                        insert(now^(pl2<<(j+1<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
                            val+(r==3)+(ur==3)+(u==3)+(ul==3));
                    }
                    else if(pl1&&!pl2)//2）
                    {
                        insert(now^(pl1<<(j<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
                            val+(r==3)+(ur==3)+(u==3)+(ul==3));
                        insert(now^(pl1<<(j+1<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
                            val+(r==3)+(ur==3)+(u==3)+(ul==3));
                    }
                    else if(pl1==1&&pl2==1)//3）
                        insert(right(now,j,1),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
                            val+(r==3)+(ur==3)+(u==3)+(ul==3));
                    else if(pl1==2&&pl2==2)//4）
                        insert(left(now,j,2),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
                            val+(r==3)+(ur==3)+(u==3)+(ul==3));
                    else if(pl1==2&&pl2==1)//6）
                        insert(now,stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
                            val+(r==3)+(ur==3)+(u==3)+(ul==3));
                    else if(pl1==1&&pl2==3)//7）
                        insert(right(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
                            val+(r==3)+(ur==3)+(u==3)+(ul==3));
                    else if(pl1==2&&pl2==3)//8）
                        insert(left(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
                            val+(r==3)+(ur==3)+(u==3)+(ul==3));
                    else if(pl1==3&&pl2==1)//7）
                        insert(right(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
                            val+(r==3)+(ur==3)+(u==3)+(ul==3));
                    else if(pl1==3&&pl2==2)//8）
                        insert(left(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
                            val+(r==3)+(ur==3)+(u==3)+(ul==3));
                    else if(pl1==3&&pl2==3)//9）
                        insert(now,stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
                            val+(r==3)+(ur==3)+(u==3)+(ul==3));
                }
                else if(c[i][j]=='S'||c[i][j]=='T')//4
                {
                    if(c[i][j]=='S'&&!pl1&&!pl2)//1）
                    {
                        insert(now^(3<<(j<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
                            val+(r==3)+(ur==3)+(u==3)+(ul==3));
                        insert(now^(3<<(j+1<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
                            val+(r==3)+(ur==3)+(u==3)+(ul==3));
                    }
                    else if(c[i][j]=='T'&&!pl1&&!pl2)//1）
                    {
                        insert(now^(3<<(j<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
                            val+(r==3)+(ur==3)+(u==3)+(ul==3));
                        insert(now^(3<<(j+1<<1)),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
                            val+(r==3)+(ur==3)+(u==3)+(ul==3));
                    }
                    else if(!pl1&&pl2==1)//2）
                        insert(right(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
                            val+(r==3)+(ur==3)+(u==3)+(ul==3));
                    else if(!pl1&&pl2==2)//3）
                        insert(left(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
                            val+(r==3)+(ur==3)+(u==3)+(ul==3));
                    else if(pl1==1&&!pl2)//2）
                        insert(right(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
                            val+(r==3)+(ur==3)+(u==3)+(ul==3));
                    else if(pl1==2&&!pl2)//3）
                        insert(left(now,j,3),stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
                            val+(r==3)+(ur==3)+(u==3)+(ul==3));
                    else if(pl1==3&&!pl2)//4）
                        insert(now,stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
                            val+(r==3)+(ur==3)+(u==3)+(ul==3));
                    else if(!pl1&&pl2==3)//4）
                        insert(now,stb^(ur<<(j+1<<1))^(1<<(j+1<<1)),stc,
                            val+(r==3)+(ur==3)+(u==3)+(ul==3));
                }
            }
        }
    }
    int ans=0;
    for(int i=1;i<=cnt[now];i++)//统计答案
        if(!fst[now][0][i])
            ans=max(ans,f[now][i]);
    printf("%lld",ans);
    return 0;
}