P3190 [HNOI2007]神奇游乐园

Description

给你一个 \(m * n\) 的矩阵，每个矩阵内有个权值\(V(i,j)\) (可能为负数)，要求找一条回路，使得每个点最多经过一次，并且经过的点权值之和最大。

Input

输入文件中的第一行为两个正整数\(n\)和\(m\)，表示游乐场的大小为\(n*m\)。因为这个娱乐场很狭窄，所以\(n\)和\(m\)满足：\(2\le n\le 100\)，\(2\le m\le 6\)。接下来的\(n\)行，每行有\(m\)个整数，第\(i\)行第\(j\)列表示游乐场的第\(i\)行第\(j\)列的小格子中的娱乐项目的满意度，这个满意度的范围是\([-1000，1000]\)。同一行的两个整数之间用空格隔开。

Output

输出文件中仅一行为一个整数，表示最高的满意度之和。

注意几个问题

什么时候更新答案？

当前格子左边是\(1\)，上边是\(2\)且除去这个\(1\)和\(2\)后的状态上没有插头。
每次新一行的时候我们会把状态数组向右移动两位，这时候会当\(n\)比较大的时候出现负数，在插入\(Hash\)表取模后需要把\(Ta\)变成正数。

当然也可以有其他的方法，用无符号整型自然溢出或者手动每次\(\&\)一个状态内全是\(1\)，其余的位置全是\(0\)的数字。实测每次\(\&\)的速度是最快的，大概是其他两个的\(1/8\)。
- 其实写的漂亮并不会出现负数
- 但是一出现可能挂的很惨哦
在伸出插头时一定要注意边界，不能越过\(n\)和\(m\)

Code:

#include <cstdio>

#include <cstring>

const int N=3e5;

const int mod=299987;

int n,m,cur,bit[12],ans=-0x3f3f3f3f,a[110][10];

int head[N],to[N],Next[N],cnt[2],tot,dp[2][N],sta[2][N],del;

void Ins(int s,int val)

{

    s=s&del;

    int x=s%mod;

    for(int i=head[x];i;i=Next[i])

        if(sta[cur][to[i]]==s)

        {

            dp[cur][to[i]]=dp[cur][to[i]]>val?dp[cur][to[i]]:val;

            return;

        }

    sta[cur][++cnt[cur]]=s;

    dp[cur][cnt[cur]]=val;

    to[++tot]=cnt[cur];

    Next[tot]=head[x];

    head[x]=tot;

}

void DP()

{

    dp[cur][++cnt[cur]]=0,sta[cur][cnt[cur]]=0;

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

    {

        for(int s=1;s<=cnt[cur];s++) sta[cur][s]=(sta[cur][s]<<2)&(del);

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

        {

            cur^=1;

            tot=cnt[cur]=0;

            memset(head,0,sizeof(head));

            for(int s=1;s<=cnt[cur^1];s++)

            {

                int lassta=sta[cur^1][s],lasans=dp[cur^1][s];

                int sr=lassta>>bit[j-1]&3,sd=lassta>>bit[j]&3;

                if(!sr&&!sd)

                {

                    Ins(lassta,lasans);//没选

                    Ins(lassta|(1<<bit[j-1])|(2<<bit[j]),lasans+a[i][j]);//选

                }

                else if(!sr&&sd)

                {

                    if(j<m) Ins(lassta,lasans+a[i][j]);

                    if(i<n) Ins((lassta|(sd<<bit[j-1]))&(~(sd<<bit[j])),lasans+a[i][j]);

                }

                else if(sr&&!sd)

                {

                    if(i<n) Ins(lassta,lasans+a[i][j]);

                    if(j<m) Ins((lassta|(sr<<bit[j]))&(~(sr<<bit[j-1])),lasans+a[i][j]);

                }

                else if(sr==1&&sd==1)

                {

                    int ct=1;

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

                    {

                        if((lassta>>bit[k-1]&3)==1) ++ct;

                        if((lassta>>bit[k-1]&3)==2) --ct;

                        if(!ct)

                        {

                            Ins((lassta&(~(sr<<bit[j-1])&(~(sd<<bit[j]))))-(1<<bit[k-1]),lasans+a[i][j]);

                            break;

                        }

                    }

                }

                else if(sr==2&&sd==2)

                {

                    int ct=1;

                    for(int k=j-1;k;k--)

                    {

                        if((lassta>>bit[k-1]&3)==2) ++ct;

                        if((lassta>>bit[k-1]&3)==1) --ct;

                        if(!ct)

                        {

                            Ins((lassta&(~(sr<<bit[j-1])&(~(sd<<bit[j]))))+(1<<bit[k-1]),lasans+a[i][j]);

                            break;

                        }

                    }

                }

                else if(sr==2&&sd==1)

                    Ins(lassta&(~(sr<<bit[j-1])&(~(sd<<bit[j]))),lasans+a[i][j]);

                else if(sr==1&&sd==2&&!(lassta&(~(sr<<bit[j-1]))&(~(sd<<bit[j]))&del))

                    ans=ans>lasans+a[i][j]?ans:lasans+a[i][j];

            }

        }

    }

}

int main()

{

    for(int i=1;i<=10;i++) bit[i]=i<<1;

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

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

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

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

    del=(1<<(m+1<<1|1))-1;

    DP();

    printf("%d\n",ans);

    return 0;

}

2018.12.20

巴特西

洛谷 P3190 [HNOI2007]神奇游乐园解题报告

P3190 [HNOI2007]神奇游乐园

Description

Input

Output

最新文章

热门文章

巴特西

洛谷 P3190 [HNOI2007]神奇游乐园 解题报告

P3190 [HNOI2007]神奇游乐园

Description

Input

Output

最新文章

热门文章

洛谷 P3190 [HNOI2007]神奇游乐园解题报告