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

· · 题解

本文的实现要比常规插头 DP 要复杂（即分类讨论的情形更多）。但是，其思想（大概）会比常规插头DP要更加简单。一句话，本文比较无脑硬上。同时，码量在删去注释后应该比常规插头 DP 有优势（因为除了分类讨论外细节不多）。

首先先默认 n>m，再令下标自 0 开始。

一个简单的观察是必定存在一种最优状态使得路径唯一——因为障碍数量无限制，所以自然可以堵死那些敌人不会去的地方。这样便是有关路径的统计，又是网格图，考虑插头 DP。

但是我们发现插头 DP 并不好，因为并非所有信息都能用插头表示，一个典型的例子是格子中有无炮台。因此，我们考虑压缩轮廓线周围的方格而非插头。

因为一个炮台影响八连通的格子，所以一个显然的想法是压缩 m+1 个格子的状态。假如当前决策点是 (x,y)，则状态中应该存储第 x 行中 0\sim y-1 位置的状态，以及第 x-1 行中 y-1\sim m-1 位置的状态。这样在决策 (x,y) 时，所有它能影响到以及能影响到它的位置全部被记录在状态中了。

然后我们考虑状态的每一位填什么、各表示什么意义：

  1. 这个格子放置了障碍。
  2. 这个格子是路径中某一段的左端点。
  3. 这个格子是路径中某一段的右端点。
  4. 这个格子在路径上，但不是端点。
  5. 这个格子是端点，但是此段路径的另一个端点是起点/终点。
  6. 这个格子放置了炮台。
  7. 这个格子是某一段路径的起点。（也即，其同时是1和2）。

除了状态6其它都比较好理解，唯独状态6比较奇怪。但是事实上仔细一想这是正常的，因为我们记录的是方格状态而非插头状态，如果记录的是插头那么6就可以用一个下插头+一个右插头表示，但是方格就只能老老实实新建状态表示。

因为仅仅是编号就太抽象了，所以我们将所有状态用一个形容词来修饰一下：

用8进制压缩7进制是老生常谈了。f(x,y,w,k) 表示待决策的格子是 (x,y)、填入炮台数是 w、状态是 k 时的答案应该也不难想到。然后现在我们来考虑如何转移。

附：我最近找到一种形象地给网格图上变量取名的好方法。我们可以看向键盘。

QWERTYUIOP
ASDFGHJKL
ZXCVBNM

假如我们当前关心的格子是 J 的话，就可以轻松得到其它方位的变量的命名：左侧是 H，左上是 Y，上方是 U，右上是 I。这几个位置是我们决策 J 时需要知道的信息。

至于为什么选择 J 而不选其它字符嘛，因为其它字符周边的区域中的大写字符已经被我占用了。

甚至可以出一道题目：键盘上有一些大写字符已经被占用，求最多能挖出几块这样的区域。

然后发现这也可以用轮廓线DP解决。

好那么我们现在考虑转移。

首先，当前格 J 填入非绝缘状态（即是路径的一部分）和填入5时对答案的贡献可以由 H,Y,U,I 四个状态处理得到。

然后，我们考虑转移。

首先先考虑 (x,y) 填入的东西并非由 H,U 的状态延伸而来的情形。

其它所有状态都是由 H,U 的状态延伸或拼接而成的。所以这时，如果格子有障碍，就可以直接 continue 了——障碍格显然不能成为延伸或拼接的去处。

不重不漏，讨论完毕。

代码（附有详细注释）：

#include<bits/stdc++.h>
using namespace std;
const int fni=0xc0c0c0c0;
int n,m,p,hs[2100000],sta[50000],cnt,res;
void pr(int x){for(int i=0;i<=m;i++)printf("%d",(x>>i*3)&7);}
int f[2][16][50000];
//0:block 1:left plug 2:right plug 3:part of the route 4:free plug 5:cannon 6:bi-direction plug
//0&5 are 'insulated',which do not act with any state.
//3 is 'inert',which cannot expand.
//6 is 'hyperactive',which has the necessity of expanding in both directions.
//4 is 'parasitic',which need a 1/2 plug to produce, otherwise it is as difficult as 6 when to be produced.
//1&2 are 'mundane',which do not have strong characteristics.
//all plugs except the 'insulated' 0&5 and the 'inert' 3, once put above, will always expand.
char s[30][30];
int num[30];
void dfs1(int pos,int msk,int fre,int tms){
    if(pos==m+1){
        if(tms)return;
        for(int i=1;i<pos;i++){
            if((num[i]==1||num[i]==2||num[i]==4)&&num[i-1]==3&&num[i+1]==3)return;
            if(num[i]==6&&(num[i-1]==3||num[i+1]==3))return;
        }
        cnt++,hs[msk]=cnt,sta[cnt]=msk;
        return;
    }
    num[pos]=0;dfs1(pos+1,msk,fre,tms);
    num[pos]=3,dfs1(pos+1,msk+(3<<pos*3),fre,tms);
    num[pos]=5;dfs1(pos+1,msk+(5<<pos*3),fre,tms);
    if(!pos||num[pos-1]==0||num[pos-1]==5){
        num[pos]=1,dfs1(pos+1,msk+(1<<pos*3),fre,tms+1);
        num[pos]=6,dfs1(pos+1,msk+(6<<pos*3),fre,tms);
    }
    if(!pos||(num[pos-1]!=2&&num[pos-1]!=6&&num[pos-1]!=4))num[pos]=2,dfs1(pos+1,msk+(2<<pos*3),fre,tms-1);
    if((!pos||num[pos-1]==0||num[pos-1]==5||num[pos-1]==3)&&fre<2)num[pos]=4,dfs1(pos+1,msk+(4<<pos*3),fre+1,tms);
}
int nex(int y,int k){
    if(y==m-1){
        int L=k>>m*3;k-=(L<<m*3);
        if(L!=0&&L!=3&&L!=5)return 0;
        return hs[k<<3];
    }
    return hs[k];
}
int P=0,Q=1;
void chmx(int j,int w,int id,int nw,int K,int bon=0){
    int nid=nex(j,K);
//  printf("%d:",nid),pr(K),puts("");
    if(nid&&nw<=p)f[Q][nw][nid]=max(f[Q][nw][nid],f[P][w][id]+bon);
}
int nex2(int y,int K){
    for(int i=y,j=0;i<=m;i++){
        if(((K>>i*3)&7)==1)j++;
        if(((K>>i*3)&7)==2&&!j--)return i;
    }
}
int las1(int y,int K){
    for(int i=y,j=0;i>=0;i--){
        if(((K>>i*3)&7)==2)j++;
        if(((K>>i*3)&7)==1&&!j--)return i;
    }
}
int main(){
    scanf("%d%d%d",&n,&m,&p);
    for(int i=0;i<n;i++)scanf("%s",s[i]);
    if(n<m){
        for(int i=0;i<n;i++)for(int j=i+1;j<m;j++)swap(s[i][j],s[j][i]);
        swap(n,m); 
    }
    dfs1(0,0,0,0);
//  printf("%d\n",cnt);
//  for(int i=1;i<=cnt;i++)pr(sta[i]),puts("");
    memset(f[P],fni,sizeof(f[P]));
    f[P][0][hs[0]]=0;
    for(int i=0;i<n;i++)for(int j=0;j<m;j++,P^=1,Q^=1){
        memset(f[Q],fni,sizeof(f[Q]));
        for(int w=0;w<=p;w++)for(int id=1;id<=cnt;id++){
            if(f[P][w][id]<0)continue;
            int k=sta[id];
//          printf("(%d,%d)[%d,%d]",i,j,w,id);pr(k);printf(":%d\n",f[P][w][id]);
            int H=0,Y=(k>>j*3)&7,U=(k>>(j+1)*3)&7,I=(k>>(j+2)*3)&7;
            if(U==6)continue;
            //impossible to have 6 above, as 'hyperactive' 6 is 'hyper', will immediately fission into 1&2.
            int K=k-(Y<<j*3),KHU=K;
            K-=(U<<(j+1)*3);int KH=K;
            if(j)H=((k>>(j-1)*3)&7),K-=(H<<(j-1)*3);
            int bon=(H==5)+(Y==5)+(U==5)+(I==5);
            int nob=(H!=0&&H!=5)+(Y!=0&&Y!=5)+(U!=0&&U!=5)+(I!=0&&I!=5);
            if((H==0||H==5)&&(U==0||U==5)&&s[i][j]!='#'){
                //situation of producing 'hyperactive' 6 and 'parasitic' 4(when it does not parasitize)
                if(s[i][j]=='S'||s[i][j]=='T')chmx(j,w,id,w,KHU+(4<<j*3),bon);
                else chmx(j,w,id,w,KHU+(6<<j*3),bon);
            }
            if(H!=6&&(U==0||U==5||U==3)&&s[i][j]!='S'&&s[i][j]!='T'){
                //situation where it is possible to put 'insulated' 0&5 in.
                chmx(j,w,id,w,KHU);//putting 0.
                if(s[i][j]!='#')chmx(j,w,id,w+1,KHU+(5<<j*3),nob);//putting 5.
            }
            if(s[i][j]=='#')continue;//the only operation under this circumstance is putting 0.
            if(U!=0&&U!=5&&U!=3){//situation when U has to expand.
                if(H!=0&&H!=5){//two plugs meet.
                    if(s[i][j]=='S'||s[i][j]=='T')continue;//there can't be two different routes around endpoints.
                    if(H==3)continue;//H has been on a complete route.
                    if(Y!=0&&Y!=5)continue;//a 'cancer' forms, which is invalid. 
                    if(H==1&&U==1)chmx(j,w,id,w,K+(3<<(j-1)*3)+(3<<j*3)+(3<<(j+1)*3)-(1<<nex2(j,K)*3),bon);
                    //two 1s will 'alpha-fusion', turing a 2 into 1, and leaving three 3s. 
                    if(H==1&&U==2)continue;//1&2 will 'circle', which is invalid.
                    if(H==2&&U==1)chmx(j,w,id,w,K+(3<<(j-1)*3)+(3<<j*3)+(3<<(j+1)*3),bon);
                    //2&1 will 'beta-fusion',only leaving three 3s. 
                    if(H==2&&U==2)chmx(j,w,id,w,K+(3<<(j-1)*3)+(3<<j*3)+(3<<(j+1)*3)+(1<<las1(j,K)*3),bon);
                    //two 2s will 'gamma-fusion', turing an 1 into 2, and leaving three 3s.
                    if(H==6&&U==1)chmx(j,w,id,w,K+(1<<(j-1)*3)+(3<<j*3)+(3<<(j+1)*3),bon);
                    if(H==6&&U==2)chmx(j,w,id,w,K+(2<<(j-1)*3)+(3<<j*3)+(3<<(j+1)*3),bon);
                    //6 shall be seen as 1+2.
                    if(H==4&&U==4){chmx(j,w,id,w,K+(3<<(j-1)*3)+(3<<j*3)+(3<<(j+1)*3),bon);continue;}
                    //two 'parasitic' 4, forming a complete route.
                    if(H==4&&U==1||H==1&&U==4)chmx(j,w,id,w,K+(3<<(j-1)*3)+(3<<j*3)+(3<<(j+1)*3)+(2<<nex2(j,K)*3),bon);
                    if(H==4&&U==2||H==2&&U==4)chmx(j,w,id,w,K+(3<<(j-1)*3)+(3<<j*3)+(3<<(j+1)*3)+(3<<las1(j,K)*3),bon);
                    if(H==6&&U==4)chmx(j,w,id,w,K+(4<<(j-1)*3)+(3<<j*3)+(3<<(j+1)*3),bon);
                    //4 going parasitize. 
                    continue;
                }
                if(s[i][j]=='S'||s[i][j]=='T'){
                    if(U==1)chmx(j,w,id,w,KH+(3<<j*3)+(3<<(j+1)*3)+(2<<nex2(j,K)*3),bon);
                    if(U==2)chmx(j,w,id,w,KH+(3<<j*3)+(3<<(j+1)*3)+(3<<las1(j,K)*3),bon);
                    if(U==4)chmx(j,w,id,w,KH+(3<<j*3)+(3<<(j+1)*3),bon);
                    continue;
                }
                chmx(j,w,id,w,KH+(U<<j*3)+(3<<(j+1)*3),bon);
                continue;
            }
            if(H!=0&&H!=5&&H!=3){
                if(U==3)continue;
                if(s[i][j]=='S'||s[i][j]=='T'){
                    if(H==1)chmx(j,w,id,w,K+(3<<(j-1)*3)+(3<<j*3)+(2<<nex2(j,K)*3)+(U<<(j+1)*3),bon);
                    if(H==2)chmx(j,w,id,w,K+(3<<(j-1)*3)+(3<<j*3)+(3<<las1(j,K)*3)+(U<<(j+1)*3),bon);
                    if(H==4)chmx(j,w,id,w,K+(3<<(j-1)*3)+(3<<j*3)+(U<<(j+1)*3),bon);
                    if(H==6)chmx(j,w,id,w,K+(4<<(j-1)*3)+(3<<j*3)+(U<<(j+1)*3),bon);
                    continue;
                }
                if(H==1||H==2||H==4)chmx(j,w,id,w,K+(3<<(j-1)*3)+(H<<j*3)+(U<<(j+1)*3),bon);
                else chmx(j,w,id,w,K+(1<<(j-1)*3)+(2<<j*3)+(U<<(j+1)*3),bon);
            }
        }
    }
    for(int j=1;j<=cnt;j++){
        bool ok=true;
        int k=sta[j];
        for(int t=0;t<=m;t++)if(((k>>t*3)&7)!=0&&((k>>t*3)&7)!=3&&((k>>t*3)&7)!=5){ok=false;break;}
        if(!ok)continue;
        for(int i=0;i<=p;i++)res=max(res,f[P][i][j]);
    }
    printf("%d\n",res);
//  for(int i=1;i<=cnt;i++)pr(sta[i]),puts("");
    return 0;
}