题解 P3190 【[HNOI2007]神奇游乐园】

SIGSEGV

2019-03-15 20:43:33

Solution

一道~~奇怪的~~插头dp(默认你们会插头dp) ## 用不着哈希,直接存合法下标和它们对应的的值就够了 > 我的奇丑无比的代码用hash后就TLE了...... 然后是插头dp正题 --- 1. 00: 00(不开始回路)12(开始一个转角) 2. 插头里有一个是0:延长或转弯 3. 两个插头相同且不为0:如果两个都是1就改上插头对应的2,否则改左插头对应的1 4. 12: 结束回路,判断轮廓线上有没有其它插头再算答案 5. 21: 直接进行连接(相当于添加一个转角) 其中2,3,5都是与正常的插头dp相同的,只有1和4要注意一下 剩下的看代码吧 ```cpp #include <bits/stdc++.h> using namespace std; int n,m,bits[20]; inline void ch(int &val,const int &pos,const int &vv) //查询 {val &= ~(3 << bits[pos - 1]);val |= (vv << bits[pos - 1]);} inline int query(const int &val,const int &pos) //更改 { return (val >> bits[pos - 1]) & 3;} const int N = 1048576; int sub[N],val[N],l; struct DP { int ptr = 0,_sub[N],_val[N];//_sub:下标 _val:值(不用long long) bool last = 0,vis[N]; inline void clear() { memset(vis,0,sizeof(vis));ptr = last = 0; } inline void set_last() {last = 1;} //是否为最后一列 DP() {clear(); } inline void add(int s,int vv) { if (last) s <<= 2; //最后一列的特殊处理 if (vis[s]) //下标出现过 { if (_val[s] < vv) _val[s] = vv; } else { _sub[ptr++] = s;_val[s] = vv; vis[s] = 1; } } inline void fetch_all() //获取所有 { l = 0; for (int i = 0;i < ptr;i++) { sub[++l] = _sub[i]; val[l] = _val[_sub[i]]; } } } h[2]; int a[105][10],ans; int find_pos(int cur,int pos,int dirc) { int tmp = query(cur,pos),top = 0; if (tmp == 1) ++top;else if (tmp == 2) --top; pos += dirc; while (1) { tmp = query(cur,pos); if (tmp == 1) ++top;else if (tmp == 2) --top; if (top == 0) return pos; pos += dirc; } } void dp(int now,int i,int j) { int pre = now ^ 1,cnt = 0; if (j == m) h[now].set_last(); h[pre].fetch_all(); for (int k = 1;k <= l;k++) { int stat = sub[k],cur = sub[k],vv = val[k] + a[i][j]; int left = query(stat,j),up = query(stat,j + 1); ++cnt; if (left == 0 && up == 0) //Case 1 { h[now].add(stat,vv - a[i][j]); if (i == n || j == m) continue; ch(cur,j,1);ch(cur,j + 1,2);h[now].add(cur,vv); } else if (left == 0 || up == 0) //Case 2 { if (i != n) { ch(cur,j,left + up);ch(cur,j + 1,0);h[now].add(cur,vv); } if (j != m) { ch(cur,j,0);ch(cur,j + 1,left + up);h[now].add(cur,vv); } } else if (left == up) //Case 3 { if (left == 1) { ch(cur,find_pos(stat,j + 1,1),1); ch(cur,j,0);ch(cur,j + 1,0);h[now].add(cur,vv); } else if (left == 2) { ch(cur,find_pos(stat,j,-1),2); ch(cur,j,0);ch(cur,j + 1,0);h[now].add(cur,vv); } } else if (left == 1 && up == 2) //Case 4 { ch(cur,j,0);ch(cur,j + 1,0);if (!cur) ans = max(ans,vv); } else if (left == 2 && up == 1) //Case 5 { ch(cur,j,0);ch(cur,j + 1,0);h[now].add(cur,vv); } } } int main () { for (int i = 0;i < 20;i++) bits[i] = (i << 1); int num = 0;ch(num,1,2); scanf("%d%d",&n,&m); for (int i = 1;i <= n;i++) for (int j = 1;j <= m;j++) scanf("%d",&a[i][j]); if (m > 6) throw; int now = 0;h[1].add(0,0); ans = INT_MIN; for (int i = 1;i <= n;i++) for (int j = 1;j <= m;j++) { dp(now,i,j);now ^= 1;h[now].clear(); } printf("%d",ans); return 0; } ```