bzoj 1187: [HNOI2007]神奇遊樂園

題意

經曆了一段艱辛的旅程後，主人公小P乘坐飛艇傳回。在傳回的途中，小P發現在漫無邊際的沙漠中，有一塊狹長的綠地特别顯眼。往下仔細一看，才發現這是一個遊樂場，專為旅途中疲憊的人設計。娛樂場可以看成是一塊大小為n×m的區域，且這個n×m的區域被分成n×m個小格子，每個小格子中就有一個娛樂項目。然而，小P并不喜歡其中的所有娛樂項目，于是，他給每個項目一個滿意度。滿意度為正時表示小P喜歡這個項目，值越大表示越喜歡。為負時表示他不喜歡，這個負數的絕對值越大表示他越不喜歡。為0時表示他對這個項目沒有喜惡。小P決定将飛艇停在某個小格中，然後每步他可以移動到相鄰的上下左右四個格子的某個格子中。小P希望找一條路徑，從飛艇所在格出發，最後又回到這個格子。小P有一個習慣，從不喜歡浪費時間。是以，他希望經過每個格子都是有意義的：他到一個地方後，就一定要感受以下那裡的驚險和刺激，不管自己是不是喜歡那裡的娛樂項目。而且，除了飛艇所在格，其他的格子他不願意經過兩次。小P希望自己至少要經過四個格子。在滿足這些條件的情況下，小P希望自己玩過的娛樂項目的滿意度之和最高。你能幫他找到這個最高的滿意度之和嗎？

題解：

直接上插頭dp……

于是愉快的wa掉。

按我的打法，有這種情況：

是以更新答案時判斷下目前年狀态是否隻有一個括号。

code：

#include<cstdio>
#include<cstdlib>
#include<cstring>
#include<iostream>
using namespace std;
const int mod=,inf=<<;
int list[][mod],state[][mod],hash[mod],num[],now,ans;
int map[][],n,m;
int get(int s,int p) {return (s>>((p-)*2))&;}
void change(int &s,int p,int c) {s^=get(s,p)<<((p-)*2);s^=c<<((p-)*2);}
void update(int &x,int y) {x=x>y?x:y;}
void add(int st,int sum)
{
    int s=st%mod;
    while(hash[s]&&list[now][hash[s]!=st]) (s+=)%=mod;
    if(!hash[s]) hash[s]=++num[now],list[now][num[now]]=st,state[now][num[now]]=sum;
    else update(state[now][hash[s]],sum);
}
bool check(int st)
{
    int tot=;
    for(int i=;i<=m+;i++) if(get(st,i)) tot++;
    return tot==;
}
void solve()
{
    state[][]=list[][]=now=;num[]=;ans=-inf;
    for(int i=;i<=n;i++)
    {
        for(int j=;j<=m;j++)
        {
            now^=;num[now]=;memset(hash,,sizeof(hash));
            for(int k=;k<=num[!now];k++)
            {
                int st=list[!now][k],p=get(st,j),q=get(st,j+),sum=state[!now][k];
                if(!p&&!q)
                {
                    add(st,sum);
                    if(i+<=n&&j+<=m) change(st,j,),change(st,j+,),add(st,sum+map[i][j]);
                }
                else if(!p&&q)
                {
                    if(j+<=m) add(st,sum+map[i][j]);
                    if(i+<=n) change(st,j,q),change(st,j+,),add(st,sum+map[i][j]);
                }
                else if(p&&!q)
                {
                    if(i+<=n) add(st,sum+map[i][j]);
                    if(j+<=m) change(st,j,),change(st,j+,p),add(st,sum+map[i][j]);
                }
                else if(p==&&q==) {if(check(st)) update(ans,sum+map[i][j]);}
                else if(p==&&q==) {change(st,j,);change(st,j+,);add(st,sum+map[i][j]);}
                else if(p==&&q==)
                {

                    int top=;
                    for(int pos=j+;pos<=m+;pos++)
                    {
                        int tmp=get(st,pos);
                        if(tmp==) top++;if(tmp==) top--;
                        if(!top) {change(st,j,);change(st,j+,);change(st,pos,);add(st,sum+map[i][j]);break;}
                    }
                }
                else if(p==&&q==)
                {

                    int top=;
                    for(int pos=j-;pos;pos--)
                    {
                        int tmp=get(st,pos);
                        if(tmp==) top++;if(tmp==) top--;
                        if(!top) {change(st,j,);change(st,j+,);change(st,pos,);add(st,sum+map[i][j]);break;}
                    }
                }
            }
        }
        for(int j=;j<=num[now];j++) list[now][j]<<=;
    }
}
int main()
{
    scanf("%d %d",&n,&m);
    for(int i=;i<=n;i++)
        for(int j=;j<=m;j++) scanf("%d",&map[i][j]);
    solve();printf("%d",ans);
}