[HNOI2007]神奇游乐园（插头DP）

题意：n*m的矩阵内值有正有负，找一个四连通的简单环（长度>=4），使得环上值的和最大。

题解：看到2<=m<=6和简单环，很容易想到插头DP，设f[i][j][k]表示轮廓线为第i行第j列，插头状态为k的最大满意度。然后又成了一道插头DP的板子题。注意左插头为左括号，上插头为右括号，其余位置无插头，因为题目不要求走遍所有格子，且只能走一条回路。

#include<bits/stdc++.h>

using namespace std;

const int N=,mod=;

int n,m,ans,p,bin[],w[][],a[][N],f[][N],tot[N],hd[N],nxt[N];

void add(int S,int v)

{

    int u=S%mod;

    for(int i=hd[u];i;i=nxt[i])if(a[p][i]==S){f[p][i]=max(f[p][i],v);return;}

    a[p][++tot[p]]=S,nxt[tot[p]]=hd[u],hd[u]=tot[p],f[p][tot[p]]=v;

}

int main()

{

    scanf("%d%d",&n,&m);

    ans=-1e9;

    for(int i=;i<=n;i++)

    for(int j=;j<=m;j++)

    scanf("%d",&w[i][j]);

    bin[]=;for(int i=;i<=;i++)bin[i]=bin[i-]<<;

    tot[p]=;

    for(int i=;i<=n;i++)

    {

        for(int j=;j<=tot[p];j++)a[p][j]<<=;

        for(int j=;j<=m;j++)

        {

            p^=;

            memset(hd,,sizeof hd);

            tot[p]=;

            for(int k=;k<=tot[p^];k++)

            {

                int S=a[p^][k],b1=(S>>j*-)%,b2=(S>>j*)%,val=f[p^][k];

                if(!b1&&!b2)

                {

                    if(i<n&&j<m)add(S+bin[j-]+*bin[j],val+w[i][j]);

                    add(S,val);

                }

                else if(!b1&&b2)

                {

                    if(j<m)add(S,val+w[i][j]);

                    if(i<n)add(S-b2*bin[j]+b2*bin[j-],val+w[i][j]);

                }

                else if(b1&&!b2)

                {

                    if(j<m)add(S-b1*bin[j-]+b1*bin[j],val+w[i][j]);

                    if(i<n)add(S,val+w[i][j]);

                }

                else if(b1==&&b2==)

                {

                    int k1=;

                    for(int t=j+;t<=m;++t)

                    {

                        if((S>>t*)%==)k1++;

                        if((S>>t*)%==)k1--;

                        if(!k1){add(S-bin[j-]-bin[j]-bin[t],val+w[i][j]);break;}

                    }

                }

                else if(b1==&&b2==)

                {

                    int k1=;

                    for(int t=j-;t>=;--t)

                    {

                        if((S>>t*)%==)k1--;

                        if((S>>t*)%==)k1++;

                        if(!k1){add(S-*bin[j-]-*bin[j]+bin[t],val+w[i][j]);break;}

                    }

                }

                else if(b1==&&b2==)add(S-*bin[j-]-bin[j],val+w[i][j]);

                else if(S-bin[j-]-*bin[j]==)ans=max(ans,val+w[i][j]);

            }

        }

    }

    printf("%d",ans);

}

巴特西

[HNOI2007]神奇游乐园（插头DP）

最新文章

热门文章