题解 P3190 【[HNOI2007]神奇游乐园】
SIGSEGV
2019-03-15 20:43:33
一道~~奇怪的~~插头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;
}
```