BZOJ1187:[HNOI2007]神奇游乐园 插头dp
思路:
非常裸的插头dp,只不过这道题是只有一条回路,这个很容易实现,当遇到左右插头合并的时候直接更新答案,而并不是向下转移.
然后这个是要维护一个左右插头,我们用三进制来维护.
具体转移时有几个细节:
不能在边界上插插头!
更新答案时必须确认当前只有左右插头各一个!
我写了一个结构体来维护插头,还是蛮好写的.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 101 102 103 104 105 106 107 108 109 | #include<cstdio>#include<cstring>#include<cctype>#include<climits>#include<iostream>#include<algorithm>using namespace std;int l;struct Line{ int d[7]; Line(){memset(d,0,sizeof d);} inline int hash(){ int re=0,mi=1;for(int i=0;i<l;++i,mi*=3)re+=d[i]*mi;return re; } inline void flush(){ for(int i=l-1;i>=1;--i)d[i]=d[i-1];d[0]=0; } inline int getleftins(int x){ int sav=0; for(int i=x;i>=0;--i){ if(d[i]==2)++sav;else if(d[i]==1)--sav; if(sav==0)return i; } } inline int getrightins(int x){ int sav=0; for(int i=x;i<l;++i){ if(d[i]==1)++sav;else if(d[i]==2)--sav; if(sav==0)return i; } } Line change(int ins,int x){ Line re=*this;re.d[ins]=x;return re; } inline int getlnum(){ int re=0;for(int i=0;i<l;++i)re+=d[i]==1;return re; } inline int getrnum(){ int re=0;for(int i=0;i<l;++i)re+=d[i]==2;return re; }};struct Hashset{ int ins[2187],w[2187],ind; Line s[2187]; inline void reset(){ind=0,memset(ins,-1,sizeof ins);} inline void insert(Line l,int _w){ int hash=l.hash(); if(ins[hash]==-1)ins[hash]=ind,w[ind]=_w,s[ind++]=l; else w[ins[hash]]=max(w[ins[hash]],_w); }}S[2];#define N 110#define M 10int w[N][M];int main(){ int n,m;scanf("%d%d",&n,&m);register int i,j,k;l=m+1; for(i=1;i<=n;++i)for(j=1;j<=m;++j)scanf("%d",&w[i][j]); int now=0,last=1; Line begin;S[now].reset(),S[now].insert(begin,0); int res=-1<<30; Line nowst;int nowf,d1,d2,ins1,ins2; for(i=1;i<=n;++i){ for(j=1;j<=m;++j){ swap(now,last),S[now].reset(); for(k=0;k<S[last].ind;++k){ nowst=S[last].s[k];nowf=S[last].w[k]; d1=nowst.d[j-1],d2=nowst.d[j]; if(d1==0&&d2==0){ S[now].insert(nowst,nowf); if(i!=n&&j!=m)S[now].insert(nowst.change(j-1,1).change(j,2),nowf+w[i][j]); } else if(d1==0||d2==0){ if(i!=n)S[now].insert(nowst.change(j-1,d1+d2).change(j,0),nowf+w[i][j]); if(j!=m)S[now].insert(nowst.change(j-1,0).change(j,d1+d2),nowf+w[i][j]); } else if(d1==1&&d2==1){ ins1=nowst.getrightins(j),ins2=nowst.getrightins(j-1); S[now].insert(nowst.change(j-1,0).change(j,0).change(ins1,1).change(ins2,2),nowf+w[i][j]); } else if(d1==1&&d2==2){ if(nowst.getlnum()==1&&nowst.getrnum()==1)res=max(res,nowf+w[i][j]); } else if(d1==2&&d2==1){ S[now].insert(nowst.change(j-1,0).change(j,0),nowf+w[i][j]); } else if(d1==2&&d2==2){ ins1=nowst.getleftins(j),ins2=nowst.getleftins(j-1); S[now].insert(nowst.change(j-1,0).change(j,0).change(ins1,1).change(ins2,2),nowf+w[i][j]); } } } swap(now,last),S[now].reset(); for(k=0;k<S[last].ind;++k){ nowst=S[last].s[k],nowf=S[last].w[k]; nowst.flush(); S[now].insert(nowst,nowf); } } printf("%d",res); return 0;} |
评论 (0)