group 状压dp

逃离我推掉我的手 2023-08-17 16:48 137阅读 0赞

应某些人要求，我把标签删掉了

这是一道好题。

一看$c<=16$果断状压，但是怎么压？

一个很显然的思路是，枚举上下两层的状态，每一层的状态极限有$C（c，c/2）$,c=16的时候有13000左右，显然是死掉了。

我们考虑换个角度。上下两层的状态数太多，那我们不妨只考虑一层，而每个点只与它上下左右四个点有关，在dp的时候也只需要考虑上面和左边的数，多余的点在转移完右边和下边之后就失去了用处，那么我们不妨扔掉它们。

想到这个之后这道题就比较简单了。

我们令$f\[i\]\[j\]\[k\]$表示当前考虑第i行第j个位置，状态为k时候的状态数，转移思路和插头dp有些类似，考虑当前格上面和左边是否有字母转移即可

这道题很多思路都和插头dp有些相近的地方。

理论复杂度$O(rc2^c)$，实际则远远达不到（达到了复杂度也是对的）

1 #include<bits/stdc++.h>
     2 using namespace std;
     3 int r,c,cur,la,ans;
     4 char s[130][55];
     5 struct hash_map{
     6     int fi[23333],ne[6000005];
     7     int val[6000006],tot,f[6000005];
     8     inline void clear(){
     9         tot=0;memset(fi,0,sizeof(fi));
    10     }
    11     inline int &operator [](int x){
    12         int y=x%23333,i=fi[y];
    13         for(;i&&val[i]!=x;i=ne[i]);
    14         if(!i) ne[++tot]=fi[y],fi[y]=i=tot,val[tot]=x,f[i]=0;
    15         return f[i];
    16     }
    17 }g[2];
    18 inline int count(int x,int y){
    19     int cnt=0;
    20     for(int i=0;i<y;i++) cnt+=((x&2)>>1),x>>=1;
    21     return cnt;
    22 }
    23 inline int count2(int x,int y){
    24     int cnt=0;
    25     for(int i=c;i>=y;i--)
    26         if(x&(1<<i)) cnt++;
    27     return cnt;
    28 }
    29 int main(){
    30     cin>>r>>c;
    31     for(int i=1;i<=r;i++) scanf("%s",s[i]+1);
    32     g[0][0]=0;
    33     for(int i=1;i<=r;i++){
    34         int len=strlen(s[i]+1),lea=strlen(s[i-1]+1);
    35         for(int j=1;j<=c;j++){
    36             la=cur,cur^=1;g[cur].clear();
    37             for(int k=1;k<=g[la].tot;k++){
    38                 int v=g[la].val[k],f=g[la].f[k],c1=count(v,j-1),c2=lea-count2(v,j)+1;
    39                 if(len-c1>c-j+1)continue;
    40                 if((v&(1<<j-1))&&(v&(1<<j))&&c1<len) g[cur][v]=max(g[cur][v],f+(s[i][c1+1]==s[i][c1])+(s[i-1][c2]==s[i][c1+1]));
    41                 else if(v&(1<<j-1)&&c1<len) g[cur][v|(1<<j)]=max(g[cur][v|(1<<j)],f+(s[i][c1+1]==s[i][c1]));
    42                 else if(v&(1<<j)&&c1<len) g[cur][v]=max(g[cur][v],f+(s[i][c1+1]==s[i-1][c2]));
    43                 else if(c1<len) g[cur][v|(1<<j)]=max(g[cur][v|(1<<j)],f);
    44                 if(len-c1<=c-j)g[cur][(v|(1<<j))^(1<<j)]=max(g[cur][(v|(1<<j))^(1<<j)],f);
    45             }
    46         }
    47     }
    48     for(int i=1;i<=g[cur].tot;i++)
    49         if(count(g[cur].val[i],c)==strlen(s[r]+1))
    50             ans=max(ans,g[cur].f[i]);
    51     printf("%d\n",ans<<1);
    52     return 0;
    53 }

转载于:https://www.cnblogs.com/hzoi-cbx/p/11566865.html