题目描述
经历了一段艰辛的旅程后,主人公小P乘坐飞艇返回。在返回的途中,小P发现在漫无边际的沙漠中,有一块狭长的绿地特别显眼。往下仔细一看,才发现这是一个游乐场,专为旅途中疲惫的人设计。娱乐场可以看成是一块大小为的区域,且这个
的区域被分成
个小格子,每个小格子中就有一个娱乐项目。然而,小P并不喜欢其中的所有娱乐项目,于是,他给每个项目一个满意度。满意度为正时表示小P喜欢这个项目,值越大表示越喜欢。为负时表示他不喜欢,这个负数的绝对值越大表示他越不喜欢。为0时表示他对这个项目没有喜恶。小P决定将飞艇停在某个小格中,然后每步他可以移动到相邻的上下左右四个格子的某个格子中。小P希望找一条路径,从飞艇所在格出发,最后又回到这个格子。小P有一个习惯,从不喜欢浪费时间。因此,他希望经过每个格子都是有意义的:他到一个地方后,就一定要感受以下那里的惊险和刺激,不管自己是不是喜欢那里的娱乐项目。而且,除了飞艇所在格,其他的格子他不愿意经过两次。小P希望自己至少要经过四个格子。在满足这些条件的情况下,小P希望自己玩过的娱乐项目的满意度之和最高。你能帮他找到这个最高的满意度之和吗?
输入格式
输入文件中的第一行为两个正整数和
,表示游乐场的大小为
。因为这个娱乐场很狭窄,所以
和
满足:
。接下来的n行,每行有m个整数,第i行第j列表示游乐场的第i行第j列的小格子中的娱乐项目的满意度,这个满意度的范围是
。同一行的两个整数之间用空格隔开。
输出格式
输出文件中仅一行为一个整数,表示最高的满意度之和。
题目解析
题目所求是网格图中最大权哈密顿回路,显然是插头DP。
分析题目要求,有一些地方值得注意。首先,不必经过所有格子,那么不是每一个格子都有插头。其次,在不经过所有格子的情况下,如果按照经典方法转移的话,可能会出现多条回路。所以必须要认真考虑状态和转移。
状态还是采用括号表示法。转移要注意以下几点:
1.每个点都可以开始一个新的状态,初始权值为
。
2.合并左括号和右括号标志回路的形成。合并时需保证不存在其他插头,此时更新答案并不再向下转移。
其他情况的转移和经典问题相似,不再赘述。时间复杂度。
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 110 111 112 113 114 115 116 117 118 119 120 121 122 123 124 125 126 127 128 129 130 131 132 133 134 135 136 137 138 139 140 141 142 143 144 145 146 147 148 149 150 151 152 153 154 155 156 157 158 159 160 161 162 163 164 165 166 167 168 169 170 171 172 173 174 175 176 177 178 179 |
/************************************************************** Problem: 1187 User: frank_c1 Language: C++ Result: Accepted Time:36 ms Memory:1336 kb ****************************************************************/ #include <set> #include <map> #include <queue> #include <cmath> #include <ctime> #include <cstdio> #include <vector> #include <string> #include <bitset> #include <cctype> #include <cstring> #include <cstdlib> #include <utility> #include <iostream> #include <algorithm> #define REP(i,a,b) for(int i=(a);i<=(b);i++) #define PER(i,a,b) for(int i=(a);i>=(b);i--) #define RVC(i,S) for(int i=0;i<(S).size();i++) #define RAL(i,x) for(int i=fr[x];i!=-1;i=e[i].next) using namespace std; typedef long long LL; typedef pair<int,int> pii; template<class T> inline void read(T& num) { bool start=false,neg=false; char c; num=0; while((c=getchar())!=EOF) { if(c=='-') start=neg=true; else if(c>='0' && c<='9') { start=true; num=num*10+c-'0'; } else if(start) break; } if(neg) num=-num; } /*============ Header Template ============*/ const int INF=(int)(1e9); int n,m; struct status { static const int mo=2333; int st[mo],cnt; int key[mo]; int val[mo]; inline void clear() { cnt=0; memset(st,0,sizeof(st)); memset(key,-1,sizeof(key)); } status() {clear();} inline void print() { REP(i,1,cnt) { REP(k,0,m) { int c=(key[st[i]]>>(k<<1))&3; if(c==0) putchar('#'); if(c==1) putchar('('); if(c==2) putchar(')'); } putchar('\n'); } } int& operator [] (int k) { int p=k%mo; while(key[p]!=k && key[p]!=-1) { p++;if(p>=mo) p-=mo; } if(key[p]==-1) st[++cnt]=p,key[p]=k,val[p]=-INF; return val[p]; } }; status f[2]; int A[105][8]; int lst=0; int res=-INF; inline int info(int s,int p) { return (s>>((p-1)<<1))&3; } inline int qt(int s,int p) { int d=info(s,p)==1?1:-1,v=0; for(int i=p;;i+=d) { int c=info(s,i); if(c==1) v++; if(c==2) v--; if(v==0) return i; } return 0; } inline int modify(int s,int p,int nv) { int k=(p-1)<<1; return ((s|(3<<k))^(3<<k))|(nv<<k); } inline bool verify(int s,int p) { s=modify(s,p,0);s=modify(s,p+1,0); return s==0; } inline int init(int p) { int s=modify(0,p,1);s=modify(s,p+1,2); return s; } inline void calc(int i,int j) { int p=lst^1;f[p].clear(); if(i!=n && j!=m) f[p][init(j)]=A[i][j]; //新的开始 REP(k,1,f[lst].cnt) { int c=f[lst].key[f[lst].st[k]]; int v=f[lst].val[f[lst].st[k]]; int a=info(c,j),b=info(c,j+1); if(a==0 && b==0) { f[p][c]=max(f[p][c],v); if(i==n || j==m) continue; c=modify(c,j,1);c=modify(c,j+1,2); f[p][c]=max(f[p][c],v+A[i][j]); } if(a!=0 && b==0) { if(i!=n) f[p][c]=max(f[p][c],v+A[i][j]); c=modify(c,j,0);c=modify(c,j+1,a); if(j!=m) f[p][c]=max(f[p][c],v+A[i][j]); } if(a==0 && b!=0) { if(j!=m) f[p][c]=max(f[p][c],v+A[i][j]); c=modify(c,j,b);c=modify(c,j+1,0); if(i!=n) f[p][c]=max(f[p][c],v+A[i][j]); } if(a==1 && b==1) { c=modify(c,qt(c,j+1),1); c=modify(c,j,0);c=modify(c,j+1,0); f[p][c]=max(f[p][c],v+A[i][j]); } if(a==2 && b==2) { c=modify(c,qt(c,j),2); c=modify(c,j,0);c=modify(c,j+1,0); f[p][c]=max(f[p][c],v+A[i][j]); } if(a==2 && b==1) { c=modify(c,j,0);c=modify(c,j+1,0); f[p][c]=max(f[p][c],v+A[i][j]); } if(a==1 && b==2) { if(verify(c,j)) res=max(res,v+A[i][j]); } } lst=p; } int main() { read(n);read(m); REP(i,1,n) REP(j,1,m) read(A[i][j]); lst=0; REP(i,1,n) { REP(j,1,m) calc(i,j); REP(k,1,f[lst].cnt) f[lst].key[f[lst].st[k]]<<=2; } printf("%d\n",res); return 0; } |
-
nosta